Possible Balanced Strings

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
10 upvotes
Asked in company
Ultimate Kronos Group

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:

[ (()()), (())(), ()()() ]
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
(()()()
Sample Output 1:
1
Explanation Of Sample Input 1:
Test case 1:
For the first test case of sample output 1, three different strings can be created by removing one extra parenthesis.
Sample Input 2:
2
()())()
()()
Sample Output 2:
1
1
Explanation Of Sample Input 2:
Test case 1:
For the first test case of sample output 2, two different strings can be created by removing one extra parenthesis.

Test case 2:   
For the second test case of sample output 2, as the string is already balanced, hence we can return the original string.
Hint

Can we use the concept of Backtracking and BFS to solve thisthis??

Approaches (1)
Greedy 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.
Time Complexity

O(2 ^ N) where ‘N’ is the length of the string.

 

Here, we are calculating for each possible substring possible from the parent string and this goes on till we get an empty string. In the worst case, we will visit all possible strings (i.e 2 ^ N), and checking all strings will take O(N) time. But as the strings are small it will be constant time. Hence, our time complexity is O(2 ^ N).

Space Complexity

O(2 ^ N) where ‘N’ is the length of the string.

 

As we are generating all possible strings possible, we are storing them in a queue. So, our space complexity is O(2 ^ N)

Code Solution
(100% EXP penalty)
Possible Balanced Strings
Full screen
Console