Minimum Remove to Make Valid Parentheses

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in companies
CognizantAppleUber

Problem statement

You are given a string ‘S’ consisting of lowercase alphabets, “(“ and “)”. You need to remove the minimum number of parentheses to make the string valid and print that valid string.

A string is valid iff:

1. It is an empty string, it contains lowercase alphabets only, or
2. It can be written as (S), where ‘S’ is the valid string.
3. It can be written as AB (‘A’ concatenated with ‘B’), where ‘A’ and ‘B’ are valid strings.
For example : 
Let string be: “co(di()ng”
The valid string can be: “co(di)ng” or “codi()ng”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains a string ‘S’.
Output Format : 
For each test case, print a valid string. There are multiple answers possible, you may print any of them.

Print output of each test case 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 <= 10
1 <= |S| <= 10^5

Where |S| represents the length of the string ‘S’.    

Time Limit: 1 sec
Sample Input 1 :
2
co(di()ng
nin())jas
Sample Output 1 :
co(di)ng
nin()jas
Explanation For Sample Output 1 :
For test case 1: 
The valid string can be: “co(di)ng” or “codi()ng”.

For test case 2: 
The valid string will be: “nin()jas”.
Sample Input 2 :
2
st()))ick
abc
Sample Output 2 :
st()ick
abc
Hint

Try to check all the possibilities by removing the brackets.

Approaches (3)
Brute Force

The basic idea is to remove the brackets of the string for all the possibilities and check for the string validity. We keep the count for all the valid strings and print, which takes minimum deletion to make the string valid.

If the current character is “)” or “(“ we have two choices with us:

  1. To include it in the string.
  2. To exclude it from the string.

 

Here is the algorithm :

 

  1. Create a string (say, ‘valStr’) to store the valid string with the minimum number of deletions.
  2. Create a variable (say, ‘CNT’) to store the number of deletions needed to make the string valid and initialize it with a large number.
  3. Call the HELPER function to find the minimum number of deletions needed.
  4. Return ‘CNT’.

 

HELPER(‘S’, ‘CNT’, ‘TEMP’, ‘CURR’, ’valStr’)   (where ‘S’ is the given string, ‘CNT’ is to store the minimum number of deletions, ‘TEMP’ is the number of deletions done till the current string, and ‘CURR’ is the current string).
 

  1. Check if the size of ‘S’ is equal to 0.
    • Check if ‘CURR’ is valid by calling the isValid function.
      • Check ‘CNT’ is greater than ‘TEMP’.
        • Update ‘CNT’ to ‘TEMP.
        • Update ‘valStr’ to ‘CURR’.
    • Return.
  2. Check if ‘S[0]’ equals ‘(‘ or ‘)’.
    • Call the HELPER function recursively by updating the ‘TEMP’ to ‘TEMP’ + 1 to exclude the current character.
    • Call the HELPER function recursively again by updating ‘CURR’ to ‘CURR’ + ‘S[0]’ to include the current character.
  3. Else,
    • Call the HELPER function recursively by updating ‘CURR’ to ‘CURR’ + ‘S[0]’ to include the current character.
       

isValid(‘CURR’)  (where ‘CURR’ is the current string).
 

  1. Create a variable (say, ‘openCnt’) to store the count of open brackets and initialize it with 0.
  2. Run a loop from 0 to ‘N’ (say, iterator ‘i’).
    • Check if ‘S[i]’ is equal to ‘(‘.
      • Increase ‘openCnt’ by 1.
    • Else check if ‘S[i]’ is equal to ‘)’.
      • Check if ‘openCnt’ is equal to 0.
        • Return FALSE.
      • Else,
        • Decrease ‘openCnt’ by 1.
  3. Check if ‘openCnt’ is equal to 0.
    • Return TRUE.
  4. Else,
    • Return FALSE.
Time Complexity

O((2 ^N ) * N), where ‘N’ is the size of the string.

 

Every character equal to ‘(‘ or ‘)’ of the string has two choices, whether to include it in a string or not. There are total ‘N’ characters, so the number of possible combinations will be 2 * 2 * 2… (‘N’ times). And for every string, we check whether it is valid or not, which takes O(N) time. Therefore, the overall time complexity will be O((2 ^ N) * N).

Space Complexity

O(N), where ‘N’ is the size of the string.

 

The recursive stack for the HELPER function can contain the length of the string at most. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Minimum Remove to Make Valid Parentheses
Full screen
Console