Generating all the substrings from a string using recursion
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 using recursion.
Generating Substrings
Generating substrings from a string using recursion involves making a recursive call for each character in the string to generate substrings from it.
Inside each recursive call, for a given character, we extract a substring starting from that character and add it to the result ArrayList.
Pseudocode
make a recursive call for each character in a string
inside each recursive call , extract all the substring starting from that character.
terminate recursion (base case) when reach to the end of input string
---------------------------------------------------------------------
make a recursive call for each character in a string:
- generateSubStringsUsingRecursion(inputString,startPos+1, res);
inside each recursive call , extract all the substring starting from that character:
- for(int j=startPos; j<inputString.length();j++) {
res.add(inputString.substring(startPos, j + 1));
}
termination
- if(startPos>=inputString.length()){
return;
}
Code
- In this solution, we are generating a substring for each character. this is managed by recursion. Then for each substring, we generate substrings that start from the current character using a for loop. In each for-loop iteration, we are adding each substring to the result list.
public void generateSubStringsUsingRecursion(String inputString, int startPos, List<String> res){
// base case
if(startPos>=inputString.length()){
return;
}
// generate substring starting from char at (startPos)
for(int j=startPos; j<inputString.length();j++) {
res.add(inputString.substring(startPos, j + 1));
}
// recursive call to generate substring at startPos+1 i.e next char in string
generateSubStringsUsingRecursion(inputString,startPos+1, res);
}
Other Variant of Recursion
- In this solution, we are breaking large problems into smaller problems. So for the string “ABCD”, to find all substrings from A, we first need to calculate the substring starting from B, and to calculate the substring from B, we need to calculate the substring from C, and so on.
- For the last position in the string, we only have one substring which is a character itself.
- For other characters, we will use substring calculated at previous steps and append it to the current character along with the current character.
- Then we add the substrings generated from the current character to the global result.
public List<String> generateSubStringsUsingRecursion1(String inputString, String curr, int startPos, List<String> glRes){
if(startPos>=inputString.length()){
List<String> currList = new ArrayList<>();
currList.add(curr);
return currList;
}
List<String> subStringChars = generateSubStringsUsingRecursion1(inputString,"" + inputString.charAt(startPos), startPos + 1, glRes);
List<String> result = new ArrayList<>();
result.add(""+inputString.charAt(startPos));
if(startPos<inputString.length()-1){
for(String sub: subStringChars){
result.add(""+inputString.charAt(startPos)+sub);
}
}
glRes.addAll(result);
return result;
}
Test
- We can write a simple test to confirm if our logic works.
@Test
public void givenInputString_whenGenerateSubStrings_ThenGenerateAllStrings(){
String inputString = "ABCD";
var res = new ArrayList<String>();
generateAllSubstrings.generateSubStringsUsingRecursion(inputString, 0, res);
Collections.sort(res);
List<String> expected = expected();
assertEquals(expected, res);
}
private List<String> expected() {
return Arrays.stream("A, AB, ABC, ABCD, B, BC, BCD, C, CD, D".split(","))
.map(e -> e.replace(" ",""))
.sorted()
.toList();
}
- Similarly, we can test for the variant we discussed.
@Test
public void givenInputString_whenGenerateSubStrings_ThenGenerateAllStrings(){
String inputString = "ABCD";
var res = new ArrayList<String>();
generateAllSubstrings.generateSubStringsUsingRecursion1(inputString, "", 0, res);
Collections.sort(res);
List<String> expected = expected();
assertEquals(expected, res);
}
private 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:
O(N²) for recursion of n character and loop used for each character. Additionally, substring extraction takes O(N), which we can optimize using string concatenation. So net time complexity would be O(N²).
Space complexity:
O(N) is used to store substrings.
Conclusion
In this article, we learned about substrings and also discussed and coded substring generation in Java using a recursive approach. We discussed and coded two variants of recursion. The time complexity of generating a substring is O(N²) and while storing it takes O(N).
Code used in this example is available at github.
Before You Leave
- Crack DSA interview with Mastering Leetcode In Java — Top 100 Most Asked Problems
- Crack SQL Interview With Grokking the SQL Interview [Free Sample Copy]
- Subscribe to Java Newsletter to keep up with all the updates in Java/Spring world.