Last Updated: 3 Dec, 2021

Minimum Remove to Make Valid Parentheses

Moderate

Asked in companies

Solve now

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”.

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

Solve now

Approaches

01 Approach

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:

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

Here is the algorithm :

Create a string (say, ‘valStr’) to store the valid string with the minimum number of deletions.
Create a variable (say, ‘CNT’) to store the number of deletions needed to make the string valid and initialize it with a large number.
Call the HELPER function to find the minimum number of deletions needed.
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).

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.
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.
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).

Create a variable (say, ‘openCnt’) to store the count of open brackets and initialize it with 0.
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.
Check if ‘openCnt’ is equal to 0.
- Return TRUE.
Else,
- Return FALSE.

Solve now

02 Approach

The basic idea is to store the indices of the brackets that are not balanced in a stack. We also maintain a hashmap to store the indices that need to be removed. We traverse the string and push open brackets in the stack. If the current character is ‘)’, we check whether the top element is an open bracket and pop it else, we add the current character index in the map. We also add the indices that are present in the stack. We print the valid string without adding the index present in the map.

Here is the algorithm :

Create a stack (say, ‘ST’) to store the indices of the characters.
Create a hashmap (say, ‘MP’) to store the index to be removed.
Run a loop from 0 to ‘N’ (say, iterator ‘i’).
- Check if ‘S[i]’ equals ‘(‘.
  - Push ‘i’ in ‘ST’.
- Else, check if ‘S[i]’ is equal to ‘)’.
  - Check if the character at the index at the top of ‘ST’ is ‘(‘.
    - Pop the element from the stack.
  - Else,
    - Add ‘i’ in ‘MP’.
Run a loop till ‘ST’ is not empty.
- Add index top of ‘ST’ in ‘MP’.
- Pop it from ‘ST’.
Create a string (say, ‘valStr’) to store the valid string.
Run a loop from 0 to ‘N’ (say, iterator ‘i’).
- Check if ‘i’ is not in ‘MP’.
  - Add ‘S[i’] in ‘valStr’.
Return ‘valStr’.

Solve now

03 Approach

The basic idea is to store the count of open. We keep the count of open brackets while traversing the string and decrease its count to balance it with the closed brackets. If the count of open brackets is zero and the current character is a closed bracket, we change the value of the character at that index (say, ‘#’). We also remove the extra open brackets from the end of the string to make the string valid. We print the string excluding the ‘#’ character.

Here is the algorithm :

Create a variable (say, ‘openCnt’) to store the count of open brackets and initialize with 0.
Run a loop from 0 to ‘N’ (say, iterator ‘i’).
- Check if ‘S[i]’ equals ‘(‘.
  - Increment ‘openCnt’ by 1.
- Else, check if ‘S[i]’ is equal to ‘)’.
  - If ‘openCnt’ is equal to 0.
    - Update ‘S[i]’ to ‘#’.
  - Else,
    - Decrease ‘openCnt’ by 1.
Run a loop from ‘N’ to 0 and till ‘openCnt’ is greater than 0 (say, iterator ‘i’).
- Check if ‘S[i]’ equals ‘(‘.
  - Update ‘S[i]’ to ‘#’ and decrease ‘openCnt’ by 1.
Create a string (say, ‘valStr’) to store the valid string.
Run a loop from 0 to ‘N’ (say, iterator ‘i’).
- Check if ‘S[i]’ is not equal to ‘#’.
  - Add ‘S[i]’ to ‘valStr’.
Return ‘valStr’.

Solve now