Find all substrings of a string in "O (n^2)" time

Posted by N.K. Chauhan on Mar 31, 2024

Given a string s of length n, the task is to print all its non-empty substrings.

Input: "abc"
Output: a, ab, abc, b, bc, c

Input: "abcd"
Output: a, ab, abc, abcd, b, bc, bcd, c, cd, d

Note: For a string of length n, there are a total of n(n+1)/2 substrings. Example: "abc" has (3*4)/2 = 6 substrings i.e., "a", "ab", "abc", "b", "bc", "c".

Solutions

Method 1: Using "substring()" function

In this approach, we run two nested loops.

The outer loop picks a starting character at i th index.

The inner loop considers the picked character (j=i) and all characters on the right of it. (unitl n-1)

In each iteration of the inner loop, we use substring() function to print a substring from i to j+1.

Complexity

The time complexity of this solution is O(n^3) and space complexity is O(1).

Method 2: Using three loops

In this approach, we can run three nested loops.

The outermost loop picks a starting character at i th index.

The mid-loop considers the picked character (j=i) and all characters on the right of it. (unitl n-1)

The innermost loop prints characters from the currently picked starting point (i) to the picked ending point (j).

Complexity

The time complexity of this solution is O(n^3) and space complexity is O(1).

Method 3: Using two loops

In this approach, we run two nested loops and also use a variable "ss" to store the previous sub-string.

The outer loop picks a starting character at i th index.

The inner loop considers the picked character (j=i) and all characters on the right of it. (unitl n-1)

For a given sub-string the inner loop keeps on adding the next characters to the variable "ss" and also prints them in each iteration.

Complexity

The time complexity of this solution is O(n^2) and space complexity is O(n).

Related


Check whether the given string is a palindrome

Swap all occurrences of two characters to get lexicographically smallest string

Power Set: Print all non-empty subsequences of a string

Reverse words in a given string

Print all permutations of a given string

Check if two strings are equal or not after processing backspace

Check if two given strings are isomorphic to each other

Transform One String to Another with a Minimum Number of Operations

Print all subsequences of a string

Longest Common Prefix in an Array of Strings