Remove Invalid Parentheses - Leetcode Solution

Problem Statement:

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()" Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()" Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")(" Output: [""]

Approach:

The approach is to use BFS to search and check for valid parenthesis. The idea is to add the string to the queue from where we will start removing the parentheses. Then we remove the least amount of parentheses required to make a valid string in each iteration.

The way we check for the validity of the parentheses is by iterating through the string, adding up the counter by 1 for each opening bracket and subtracting it by 1 for each closing bracket. If the counter is negative, then it means that we have encountered a closing bracket without an opening one preceding it. In such cases, we will remove that closing bracket.

To make sure that we don’t visit the same string again, we need to use a set to store the states we have seen before. We will add the valid strings to the result list and return it.

Algorithm:

1. Initialize an empty list called “result” to store the final strings
2. Initialize an empty set called “visited” to keep the track of already visited states
3. Add the input string to the queue.
4. Loop until the queue is empty:
   1. Remove a string from the queue.
   2. If the string is valid, add it to the result list and continue; or else continue.
   3. Iterate through the string and remove each '(' and ')', and add it to the queue unless we have already visited the state.
5. Return the result list.

Code:

Here is the code for the Remove Invalid Parentheses problem.

def removeInvalidParentheses(s):
    result = []
    visited = set()
    
    queue = collections.deque([s])
    found = False
    
    while queue:
        string = queue.popleft()
        
        # if the string is valid, add it to result and mark found as True
        if isValid(string):
            result.append(string)
            found = True
        
        # if we have already found a valid string, no need to remove further parentheses
        if found:
            continue
        
        # removing a ')' or '(' from each position
        for i in range(len(string)):
            if string[i] == '(' or string[i] == ')':
                newString = string[:i] + string[i+1:]
                
                # add newString to queue only if we haven't visited it before
                if newString not in visited:
                    queue.append(newString)
                    visited.add(newString)
                    
    return result

# helper function to check if the string is valid
def isValid(s):
    count = 0
    for c in s:
        if c == '(':
            count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    
    return count == 0

Tests:

Here are the test cases to validate the solution.

print(removeInvalidParentheses("()())()"))
# Output: ["()()()", "(())()"]

print(removeInvalidParentheses("(a)())()"))
# Output: ["(a)()()", "(a())()"]

print(removeInvalidParentheses(")("))
# Output: [""]

1