Print all Possible Ways to Break a String in Bracket Form

Difficulty Level Hard
Frequently asked in Amazon Bloomberg GE Healthcare Juniper Networks
Recursion StringViews 1792

Problem Statement

In the “Print all Possible Ways to Break a String in Bracket Form” problem, we have given a string “s”. Find all possible ways to break the given string in bracket form. Enclose all substrings within brackets ().

Input Format

The first and only one line containing a string “s”.

Output Format

Print all possible ways to break the given string in bracket_form. Every line contains only one string.

Constraints

  • 1<=|s|<=10^3
  • s[i] must be a lower case English alphabet

Example

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

Algorithm

Here we use recursion to solve this problem. We maintain two parameters: The index of the next character to be processed and the output string so far. Now, start from the index of the next character to be processed. Append the substring formed by the unprocessed string to the output string and recurse on the remaining string until we process the whole string. We use std::substr to form the output string. substr(pos, n) returns a substring of length n that starts at position pos of the current string.

  1. We start from the index of the 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.

Implementation

C++ Program to Print all Possible Ways to Break a String in Bracket Form

#include <bits/stdc++.h>
using namespace std;

void find_next(string s, int in, string t)
{
  if(in==s.length())
  {	
      cout<<t<<endl;
  }
  for(int i=in;i<s.length(); i++)
  {
      string temp = t;
      temp+="(";
      temp+=s.substr(in,i+1-in);
      temp+=")";
    find_next(s, i+1 , temp);
  }
}

int main()
{
  string s;
  cin>>s;
  find_next(s,0,"");
  return 0;
}

Java Program to Print all Possible Ways to Break a String in Bracket Form

import java.util.Scanner;

class sum
{
    public static void find_next(String s, int in, String t)
    {
        if(in==s.length())
  {	
      System.out.println(t);
  }
  for(int i=in;i<s.length(); i++)
  {
      String temp = t;
      temp+="(";
      temp+=s.substring(in,i+1);
      temp+=")";
    find_next(s, i+1 , temp);
  }
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        find_next(s,0,"");
    }
}





tutcup
(t)(u)(t)(c)(u)(p)
(t)(u)(t)(c)(up)
(t)(u)(t)(cu)(p)
(t)(u)(t)(cup)
(t)(u)(tc)(u)(p)
(t)(u)(tc)(up)
(t)(u)(tcu)(p)
(t)(u)(tcup)
(t)(ut)(c)(u)(p)
(t)(ut)(c)(up)
(t)(ut)(cu)(p)
(t)(ut)(cup)
(t)(utc)(u)(p)
(t)(utc)(up)
(t)(utcu)(p)
(t)(utcup)
(tu)(t)(c)(u)(p)
(tu)(t)(c)(up)
(tu)(t)(cu)(p)
(tu)(t)(cup)
(tu)(tc)(u)(p)
(tu)(tc)(up)
(tu)(tcu)(p)
(tu)(tcup)
(tut)(c)(u)(p)
(tut)(c)(up)
(tut)(cu)(p)
(tut)(cup)
(tutc)(u)(p)
(tutc)(up)
(tutcu)(p)
(tutcup)

Complexity Analysis to Print all Possible Ways to Break a String in Bracket Form

Time Complexity

O(n^2) where n is the size of the string “s”.

Space Complexity

O(n^2) where n is the size of the string. Here we declare a string after every character for getting the answer.

Translate ยป