DEV Community

Cover image for Find all substring of a given string in O(n^2) time.
Rajesh Royal
Rajesh Royal

Posted on

Find all substring of a given string in O(n^2) time.

Below is the programmer written in JavaScript to find the all possible substrings of a given string in O(N^2) time complexity and an extra O(1) space;


function genSubstrings(inputString){
    let resultArray = [];
    // outer loop to run n times [n = size of string]
    for(let i = 0; i < inputString.length; i++){
        // pushing first char of string as substring
        // as we know that each char will be substring itself too.
        // inner loop to run n - 1 times;
        for(let j = i + 1; j < inputString.length; j++){
            // get last substring and append the new next char
              resultArray[resultArray.length - 1] + inputString[j]

    return resultArray;
Enter fullscreen mode Exit fullscreen mode



(10) ['a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd']
Enter fullscreen mode Exit fullscreen mode

I searched internet for a better solution which can run in less then O(N^2) time complexity but didn't find any.

If anyone has a better solution please write in comments, It will be really helpful.

The thumbnail is taken from geekforgeek

Top comments (3)

mistval profile image

For any given string of length n, the number of substrings is n(n + 1) / 2.

This implies an algorithm with better than O(n^2) complexity is not possible, since at a minimum you have to insert all of those n(n + 1) / 2 substrings into an array.

rajeshroyal profile image
Rajesh Royal

What if we need to print those substrings.
Do you have any code snippet of doing it.

normalgui profile image
Normal GU-I • Edited

Well, I don't think there is a better way to do this except with O(N^2); But this can be helpful - Wikipedia suffix tree