Remove Invalid Parentheses

Hard
0/120
Average time to solve is 50m
12 upvotes
Asked in companies
UberPayPalMAQ Software

Problem statement

You are given a string consisting only of parentheses and letters. Your task is to remove the minimum number of invalid parentheses and return all possible unique, valid strings thus obtained.

Note:

1) A string is valid only if every left parenthesis has corresponding right parentheses in the same order.

For example Given ‘STR’ = (())()) is not a valid string, whereas ‘STR’ = (())() is a valid string.
Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first and the only line of each test case contains a single string ‘STR’ representing the parenthesis.

Output Format:

For each test case, return all possible unique, valid strings after removing the minimum number of parentheses. 

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

Note:

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

Constraints:

1 <= T <= 5
1 <= |STR| <= 50

Time Limit: 1 second

Sample Input 1:

2
(((a))()
)(()))

Sample Output 1:

(((a))) ((a))()
(())

Explanation of Sample Output 1:

Test Case 1 :  
Given ‘STR’ = (((a))()
From this string, two valid strings can be generated after removing only one parenthesis, which is minimum.
One way is to remove the parenthesis at index 6 to generate (((a))).
Another way is to remove either the first, second, or third parenthesis, which will result in the same string, i.e., ((a))().

Test Case 2 : 
Given ‘STR’ = )(()))
The minimum number of invalid parentheses required to be removed is 2. We have to remove the first and last parentheses to generate a valid string.
So the valid string is (()).

Sample Input 2:

1
(()(()(())

Sample Output 2:

()()(()) ()(()()) (())(()) (()()()) (()(()))
Hint

Can you think of a similar approach that, by default, guarantees minimum removal of parentheses by considering strings level by level?

Approaches (3)
Breadth First Search

The idea here is to use the BFS algorithm. Using BFS, we will move through states level by the level that will ensure the removal of the minimal number of parentheses. At each level, we will remove only one parenthesis. So, if we found a valid string, we will restrict ourselves to that level only.

Please note that the overhead to pass parameters in a recursive call is also avoided because of BFS.

 

Algorithm:

  • Declare a hash set, ‘VISTED’ to keep track of the visited strings.
  • Declare a vector of string, ‘RESULT’ to store the final result.
  • Declare a queue of string, ‘Q’ for level order traversal.
  • Declare a bool variable, ‘VALID’ (initially false), that will account for the validity of the string at a level.
  • Push the string, ‘STR’ in the queue, and insert in ‘visited’ (to mark it as visited).
  • Run the loop while ‘Q’ is not empty
    • Declare a string, ‘POSSIBLE_ANSWER’, and store the front value of ‘Q’ in it.
    • Pass ‘POSSIBLE_ANSWER’ to the ‘IS_VALID_STRING’ function, where ‘IS_VALID_STRING’ checks whether the string has valid parentheses and check if ‘POSSIBLE_ANSWER’ is valid. If valid, insert the ‘POSSIBLE_ANSWER’ in ‘RESULT’ and update the ‘VALID’ to be true.
    • If VALID == true, that shows that string at this level will appear in the output. So, skip the remaining part and continue the iteration.
    • Otherwise, run a loop from i = 0 to ‘N’. Here ‘N’ is the length of the string, ‘POSSIBLE_ANSWER’.
  • If POSSIBLE_ANSWER[i] == ‘)’ or POSSIBLE_ANSWER == ‘(‘ shows that current character is a parenthesis. So, put the string after removing the current character in a string, ‘TEMP’.
    1. If VISITED.COUNT(TEMP) == 0 shows that ‘TEMP’ is not visited. So, push ‘TEMP’ in ‘Q’ and mark it visited.
  • Return the ’RESULT’.

 

Description of ‘IS_VALID_STRING’ function

 

This function will take one parameter :

  • STR: A string variable to store the original string.

 

bool IS_VALID_STRING(STR) :

  • Declare three integer variables:
    • LEFT: Stores the number of left parentheses at any instant
    • RIGHT: Stores the number of right parentheses at any instant
    • INDEX: An integer variable to iterate over the string
  • Run a loop while INDEX < STR.LENGTH()
    • If STR[INDEX] == ‘(‘ that shows that the current index is a left parenthesis. So, increment the variable ‘LEFT’.
    • Else if STR[INDEX] == ‘)’ shows that the current index is a right parenthesis. Then, we will check:
      • If LEFT > 0, that shows there is left parenthesis already present. So, we decrement the variable ‘LEFT’ to nullify the effect of the right parenthesis.
      • Else, it implies that there isn’t any left parenthesis. So, increment the variable ‘RIGHT’.
      • If RIGHT > LEFT, that shows that at this instant, the number of right parentheses has become greater than the number of left parentheses. So, the string ‘STR’ can never be valid. Therefore, return false.
    • Increment the index.
  • Return LEFT == RIGHT. So, true is returned if both are equal otherwise, false.
Time Complexity

O(N * (2 ^ N - 1)), where ‘N’ is the number of parentheses in the string.

 

Checking whether a string is valid or not will take O(N) time at each level. And, for every string of length N, we will have (N - 1) strings at the next level, i.e., C(N, N - 1) at the second level, C(N, N-2) at the third level, and so on.

Therefore, total time = N * C(N, N) + (N - 1) * C(N, N - 1) + (N - 2) * C(N, N - 2) + . . . + 1 * C(N, 1) = N * (2 ^ (N - 1)).

Space Complexity

O(N), where ‘N’ is the number of parentheses in the string.

 

We are using a queue that can take O(N) space in the worst case.

Code Solution
(100% EXP penalty)
Remove Invalid Parentheses
Full screen
Console