Blog

Generate All the Substring From a String — Iterative Approach

  • Post last modified:December 11, 2023
  • Reading time:4 mins read

Using Java to generate all the substrings from a string

Introduction

A substring is a continuous sequence of characters within a string. It is essentially a portion of the string from the start index and end index.
In this article, we will generate all the substrings from a string in Java.

Generating Substrings

To extract substrings, we need to consider starting from all the characters in the input string and form the substring starting from that character.

For example, if the input string is “ABCD”, then the first character would be ‘A’, we need to extract the substring of lengths 1,2,3,4. length 1 = ‘A’, length 2 = ‘AB’, length 3 = “ABC” and length 4 = “ABCD”. For the next character i.e. ‘B’ ( i = 1 ), we need to extract a substring of lengths 1,2,3. We will continue this for the remaining character.

At each substring formation step, we can add the extracted substring to our result list.

Pseudocode

for each character
- iterate over all the remaining string starting from the selected character
- extract the substring of length 1,2,3 ... until string is finished

------------------------------------------------------------------
for each character:
for(int i = 0; i< inputString.length(); i++){}


iterating over all the string starting from selected character i and 
finishing at the end of string:
for(int j = i+1; j<= inputString.length(); j++){ }


extracting substring of length 1,2,3 ..so on : 
res.add(inputString.substring(i, j));

Code

  • As discussed in pseudocode, we iterate for each character, which essentially means we are extracting substring starting from each character. A simple for loop would suffice for the purpose.
  • Next, we can iterate over each character starting from the selected character. In this case, our window would be a selected character defined by i index and spanning until the end of the string. j index is for expanding our window starting from i.
  • For each window, we extract a substring of length (i,j) which is the length of the window. So for i=0, j=1, we extract a substring of length 1, and for i=0, j=2, we extract a substring of length 2.. so on
public void generateSubStringsUsingForLoop(String inputString, List<String> res) {
    for(int i = 0; i< inputString.length(); i++){
        for(int j = i+1; j<= inputString.length(); j++){
            res.add(inputString.substring(i, j));
        }
    }
}

Testing

  • We can write a simple test to confirm if our logic works.
    @Test
    public void givenInputString_whenGenerateSubStrings_ThenGenerateAllStrings(){
        String inputString = "ABCD";

        var generateAllSubstrings = new GenerateAllSubstrings();
        var res =  new ArrayList<String>();
        generateAllSubstrings.generateSubStringsUsingForLoop(inputString, res);
        Collections.sort(res);
         
        List<String> expected = expected();

        assertEquals(expected, res);
   }

   
   private static List<String> expected() {
       return Arrays.stream("A, AB, ABC, ABCD, B, BC, BCD, C, CD, D".split(","))
           .map(e -> e.replace(" ",""))
           .sorted()
           .toList();
  }

Complexity

Time Complexity:
Since we are operating over two loops which is linear, we would get O(N²) time complexity for that.
Additionally, we are extracting substring from the input string, which is also an O(N) operation.
Hence time complexity becomes O(N³).

Space Complexity:
Since we are adding all the substrings to the list, our space complexity would be O(S) where S is the number of substrings.

Improvement

Our code has scope for subtle improvement. At least we can get rid of substring extraction. Instead, we can use a string builder or string concatenation (+), which may give better time complexity since it’s optimized in most programming languages.

As per my research for Java, its amortized time is constant O(1) and we can get Total Time Complexity = O(N²)

public void generateSubStringsUsingForLoop1(String inputString, List<String> res) {
    for(int i = 0; i< inputString.length(); i++){
        StringBuilder s = new Stri
        for(int j = i+1; j<= inputString.length(); j++){
            s += inputString.charAt(j-1);
            res.add(s);
        }
    }
}

Conclusion

In this article, we learned about substrings and also discussed and coded substring generation in Java using an iterative approach. Generating a substring from a string is complex in terms of time complexity since it takes O(N³) but with some improvement, it’s possible to get O(N²) complexity.

Code used in this example is available at github.

Before You Leave

Tags: , ,