Home » Technical Interview Questions » String Interview Questions » Print all possible ways to break a string in bracket form

Print all possible ways to break a string in bracket form



String

For the give input string, find all possible ways to break the given string in bracket form. Enclose all substrings within brackets ().

Examples

Input string : abcd

Output : (a)(b)(c)(d)
(a)(b)(cd)
(a)(bc)(d)
(ab)(c)(d)
(ab)(cd)
(a)(bcd)
(abc)(d)
(abcd)

Time complexity: O(n)

Algorithm

Here we use recursion, We maintain two parameters index of next character to be processed and output string so far.

1. We start from index of next character to be processed.

2. Append substring formed by unprocessed string to the output string and recur on remaining until we process the entire string.

3. We use substr(pos, n) to form the output string, this returns the substring of length n that starts at position pos if the current string.

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
void PrintCombinations(string str, int index, string output)
{
    if (index == str.length())
    {
        cout<<output<<endl;
    }
    //Recursion on remaining part of string
    for (int i = index; i < str.length(); i ++)
    {
        PrintCombinations(str, i + 1, output +"(" + str.substr(index, i+1-index) + ")" );
    }
}
 
//Main function
int main()
{
    string input_string = "abcd";
    PrintCombinations(input_string, 0, "");
    return 0;
}

Try It

 

READ  Reorganize String
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup