Solution For Remove Invalid Parentheses

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: [“”]

“`

Step by Step Implementation For Remove Invalid Parentheses

We can use a stack to keep track of the parentheses we have seen so far. If we see a '(', we push it onto the stack. If we see a ')', we check the top of the stack to see if there is a matching '('. If there is, we pop the '(' off the stack and continue processing. If there is not, we know that this ')' is invalid, so we ignore it.

At the end, we check the stack to see if there are any remaining '('. If there are, we know they are invalid and we remove them.

Given a string s of '(' , ')' and lowercase English characters. 

Your task is to remove the minimum number of parentheses ( '(' or ')' , in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

 

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"
Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.
Example 4:

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"
 

Constraints:

1 <= s.length <= 10^5
s[i] is one of  '(' , ')' and lowercase English letters.

var removeInvalidParentheses = function(s) {
    let result = [];
    let visited = new Set();
    
    let queue = [];
    queue.push(s);
    visited.add(s);
    
    let found = false;
    
    while (queue.length) {
        let curr = queue.shift();
        
        if (isValid(curr)) {
            result.push(curr);
            found = true;
        }
        
        if (found) continue;
        
        for (let i = 0; i < curr.length; i++) {
            if (curr.charAt(i) !== '(' && curr.charAt(i) !== ')') continue;
            
            let str = curr.substring(0, i) + curr.substring(i + 1);
            
            if (!visited.has(str)) {
                queue.push(str);
                visited.add(str);
            }
        }
    }
    
    return result;
};

function isValid(str) {
    let count = 0;
    
    for (let i = 0; i < str.length; i++) {
        if (str.charAt(i) === '(') count++;
        if (str.charAt(i) === ')') {
            count--;
            if (count < 0) return false;
        }
    }
    
    return count === 0;
}

We can use a stack to keep track of the parentheses we have seen so far. If we see an opening parenthesis, we push it onto the stack. If we see a closing parenthesis, we check the top of the stack to see if there is a matching opening parenthesis. If there is, we pop the opening parenthesis off the stack. If there is not, we know that this parenthesis is invalid and we should remove it.

Given a string containing only parentheses, we need to remove the minimum number of invalid parentheses in order to make the string valid. If the input string is already valid, then return 0.

We can keep track of the number of open and close parentheses we have. If at any time we have more close parentheses than open, then we need to remove a close parentheses. If we have more open parentheses than close at the end, then we need to remove some open parentheses.

public int RemoveInvalidParentheses(string s) { int open = 0, close = 0; for (int i = 0; i < s.Length; i++) { if (s[i] == '(') { open++; } else if (s[i] == ')') { if (open > 0) { open--; } else { close++; } } } return open + close; }