Remove Invalid Parentheses

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.

The idea is to explore all the possibilities by keeping two options for each parenthesis, i.e., to include or exclude. This provides us with a thought to use recursion and backtracking to solve this problem.

To check for a valid string, we will maintain the count of left and right parentheses. At any instant, if the number of left parentheses is equal to the number of right parentheses, then the string is valid; otherwise, not.

We should also keep in mind that if the number of right parentheses is greater than the number of left parentheses, then the string can never be valid. At that instant, we do not need to recur forward.

For keeping track of unique strings, we will use a hash set (i.e., unordered_set in c++).

Algorithm:

• Declare a global integer variable, ‘MIN_REMOVAL’, that will hold the minimum removals till now. Locally initialize it to INT_MAX.
• Declare a hash set of strings, ‘HASH_SET’, to store all the unique, valid strings.
• Declare a string, ‘RESULT_SO_FAR’, to store the temporary result.
• Call the ‘REMOVE_RECURSIVELY’ function to get the list of valid unique strings in ‘HASH_SET’.
• Declare a vector of strings, ‘RESULT’ to store the final result.
• Iterate over the ‘HASH_SET’ and store every string in ‘RESULT’.
• Return the ‘RESULT’.

Description of ‘REMOVE_RECURSIVELY’ function

This function will take seven parameters :

• STR: A string variable to store the original string.
• INDEX: An integer to keep track of the current index of the original string.
• RESULT_SO_FAR: A string variable to store the temporary result.
• LEFT_COUNT: An integer to keep track of the number of left parentheses.
• RIGHT_COUNT: An integer to keep track of the number of right parentheses.
• REMOVE_COUNT: An integer to keep track of the number of removals made so far.
• HASH_SET: A hash set of strings to maintain unique, valid strings.

void REMOVE_RECURSIVELY(STR, INDEX, RESULT_SO_FAR, LEFT_COUNT, RIGHT_COUNT, REMOVE_COUNT, HASH_SET):

• If INDEX == LENGTH of ‘STR’, that shows that we have tried all possible removals. So, we will check:
  • If LEFT_COUNT == RIGHT_COUNT that shows we have found a valid string. So, we will check:
    • If REMOVE_COUNT <= MIN_REMOVAL that shows the ‘RESULT_SO_FAR” is the valid candidate for the result. So, we will check:
      1. If REMOVE_COUNT < MIN_REMOVAL shows that the ‘RESULT_SO_FAR’ is the valid string obtained with minimum removal. So, clear the ‘HASH_SET’ and update ‘MIN_REMOVAL’ by ‘REMOVE_COUNT’.
    • Insert ‘RESULT_SO_FAR’ in the HASH_SET.
• Else
  • Check if STR[INDEX] != ‘(‘ and STR[INDEX] != ‘)’ that shows that the character at current index is not a parenthesis. So, push the current character in ‘RESULT_SO_FAR’ and call ‘REMOVE_RECURSIVELY’ function by updating INDEX to INDEX + 1. On returning back, pop the last inserted character.
  • Else, we will now explore both options, i.e., to include the current character or exclude the current character.
    • Include the current character in ‘RESULT_SO_FAR’.
    • If S[INDEX] == ‘(‘ that shows that the current character is a left parenthesis. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘LEFT_COUNT’ to ‘LEFT_COUNT + 1’.
    • Else current character is a right parenthesis. So, check if RIGHT_COUNT < LEFT_COUNT shows that a valid string can be found in future. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘RIGHT_COUNT’ to ‘RIGHT_COUNT + 1’.
    • Exclude the current character from ‘RESULT_SO_FAR’ and call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘REMOVE_COUNT’ to ‘REMOVE_COUNT + 1’.

The idea here is to determine the number of left and right misplaced parentheses. After that, we no longer need to check for the global minimum and update the hash set. We can be sure that if the count of both left and right misplaced parentheses reduces to zero, then the string is valid and of maximum length (formed by minimum removals).

The optimized backtracking approach will be similar to approach 1 with some modifications.

Algorithm:

• Declare three integer variables:
  • LEFT_MISPLACED: Stores the number of misplaced left parentheses
  • RIGHT_MISPLACED: Stores the number of misplaced right parentheses
  • 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_MISPLACED’.
  • Else if STR[INDEX] == ‘)’ that shows that the current index is a right parentheses. Then, we will check:
    • If LEFT_MISPLACED > 0, that shows there is a misplaced left parentheses. So, we decrement the variable ‘LEFT_MISPLACED’ to nullify the effect of the right parenthesis.
    • Else, it implies that there isn’t any misplaced left parenthesis. So, increment the variable ‘RIGHT_MISPLACED’.
  • Increment the index.
• Declare a hash set of strings, ‘HASH_SET’, to store all the unique, valid strings.
• Declare a string, ‘RESULT_SO_FAR’, to store the temporary result.
• Call the ‘REMOVE_RECURSIVELY’ function to get the list of valid unique strings in ‘HASH_SET’.
• Declare a vector of strings, ‘result’ to store the final result.
• Iterate over the ‘HASH_SET’ and store every string in ‘RESULT’.
• Return the ‘RESULT’.

Description of ‘REMOVE_RECURSIVELY’ function

This function will take eight parameters :

• STR: A string variable to store the original string.
• INDEX: An integer to keep track of the current index of the original string.
• RESULT_SO_FAR: A string variable to store the temporary result.
• LEFT_MISPLACED: An integer to keep track of the number of misplaced left parenthesis.
• RIGHT_MISPLACED: An integer to keep track of the number of misplaced right parenthesis.
• LEFT_COUNT: An integer to keep track of the number of left parentheses.
• RIGHT_COUNT: An integer to keep track of the number of right parentheses.
• HASH_SET: An unordered_set of strings to maintain unique, valid strings.

void REMOVE_RECURSIVELY(STR, INDEX, RESULT_SO_FAR, LEFT_MISPLACED, RIGHT_MISPLACED, LEFT_COUNT, RIGHT_COUNT, HASH_SET):

• If INDEX == LENGTH of ‘STR’, that shows that we have tried all possible removals. So, we will check:
  • If LEFT_MISPLACED == 0 and RIGHT_MISPLACED == 0 that shows we have found a valid string with minimum removals. So, insert ‘RESULT_SO_FAR’ in the ‘HASH_SET’ and return.
• If STR[INDEX] != ‘(‘ and STR[INDEX] != ‘)’ that shows that the character at the current index is not a parenthesis. So, push the current character in ‘RESULT_SO_FAR’ and call ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’. On returning, remove the last added character.
• Else, we will now explore both options, i.e., to include the current character or exclude the current character.
  • Include the current character in ‘RESULT_SO_FAR’.
  • If STR[INDEX] == ‘(‘ that shows that current character is a left parenthesis. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘LEFT_COUNT’ to ‘LEFT_COUNT + 1’.
  • Else current character is a right parenthesis. So, check if RIGHT_COUNT < LEFT_COUNT shows that a valid string can be found in future. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘RIGHT_COUNT’ to ‘RIGHT_COUNT + 1’.
  • Exclude the current character from ‘RESULT_SO_FAR’.
  • If STR[INDEX] == ‘(‘ and LEFT_MISPLACED > 0 that shows the current left parenthesis can be excluded. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘LEFT_MISPLACED’ to ‘LEFT_MISPLACED - 1’.
  • Else if STR[INDEX] == ‘)‘ and RIGHT_MISPLACED > 0 that shows the current right parenthesis can be excluded. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘RIGHT_MISPLACED’ to ‘RIGHT_MISPLACED - 1’.