Find all combinations of non-overlapping substrings of a string

Given a string, find all combinations of non-overlapping substrings of it. The solution should use parenthesis to split the string into non-overlapping substrings.


 

For example,


Input: ABC
Output:

(A) (B) (C)
(A) (BC)
(AB) (C)
(ABC)

 
Input: ABCD
Output:

(A) (B) (C) (D)
(A) (B) (CD)
(A) (BC) (D)
(A) (BCD)
(AB) (C) (D)
(AB) (CD)
(ABC) (D)
(ABCD)

 
The idea is to use recursion to solve this problem. For a given string of length n, we consider every prefix [0, i] of it one by one. We append the prefix to the output string by enclosing it within the parenthesis and recurse for remaining substring [i+1, n-1]. If every substring of original string is processed, we print the output string.

 
Below is C++ and Java implementation of the idea –

C++

Download   Run Code

Output:

(A) (B) (C) (D)
(A) (B) (CD)
(A) (BC) (D)
(A) (BCD)
(AB) (C) (D)
(AB) (CD)
(ABC) (D)
(ABCD)

Java

Download   Run Code

Output:

[A, B, C, D]
[A, B, CD]
[A, BC, D]
[A, BCD]
[AB, C, D]
[AB, CD]
[ABC, D]
[ABCD]

 
The time complexity of above solution is exponential as there are exactly 2n-1 combinations. Here, n is length of the input string.

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
abc
Guest

can you explain how the complexity came out to be 2^n-1? I have below implementation in C.

printsubstring(str, start, n)
{
for (k = 1; k <=size && (start + k) < n; k++)
{
print_string(str, start, start + k); // prints with paranthesis
printsubstring(str, start + k, n);
}
}