Last Updated: 2 Dec, 2020

Possible Balanced Strings

Moderate

Asked in company

Solve now

Problem statement

Ninja has been given a string S, consisting of only the '(' or ')' parenthesis. The string is not balanced, and to make the string balanced, he can remove one or more parentheses. He needs to print all possible balanced strings that can be formed from the given string by removing the minimum number of parentheses.

Note:

Print only those distinct strings that can be formed by removing the minimum number of parentheses.

If the string is already balanced, return the original string.

For example:

(()()()

Expected strings are:

[ (()()), (())(), ()()() ]

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a string ‘S’ which contains the parentheses.

Output Format:

For each case, If the returned strings are correct then the output will be 1, else  0.

The output of each test case will be printed on a separate line.

Note:

You can return strings in any order.

You do not need to input or print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= |S| <= 15

Timit Limit: 1 sec

Solve now

Approaches

01 Approach

Here, we will use the concept of Backtracking and Breadth-First Search. As we need to generate all possible output, we can backtrack among all states by removing one opening or closing bracket and check if they are valid or not. If invalid, then we can add the removed bracket back and go for the next state. We will use BFS for moving through states as the use of BFS will only remove the minimal number of brackets because we traverse into states level-wise and each level corresponds to one extra bracket removal.

Algorithm:

Declare a data structure hash-map say ‘visit’ that stores only unique strings.
Declare a Queue ‘q’ to maintain the bfs
Declare a boolean type variable ‘level’ and initialize it with false.
Declare a array arr of string type to store the result
Declare a local variable temp of string type.
Add the input string to the queue
Run a while loop till the queue is not empty
- Take out the first element from the queue
- Send this string to a function validString which will return a boolean type variable. If it returns true
  - Add this string to the array arr and set level as true
- If the level is true, go back to the while loop.
- Run a for loop ‘i’ = ‘0’ to the length of the string
  - Using substring, remove the current ith parenthesis and store it in temp
  - If temp is not present in the set
    - Push it to the queue and set ‘visit’.
Return the array

Discription of validString(s):

Declare a integer type counter variable ‘cnt’ to keep the count of the parenthesis
Run a loop ‘i’ = ‘0’ to the length of the input string
- If the current index has an opening parenthesis.
  - Increase ‘cnt’ by 1
- Else if, our current index has a closing parenthesis
  - Decrease ‘cnt’ by 1
- If ‘cnt’ becomes negative,
  - Return false as output
If ‘cnt’ is equal to 0
- Return true.

Solve now