Remove Invalid Parentheses

To solve this problem, we’ll use a breadth-first search (BFS) to explore different ways of removing parentheses and stop as soon as we find a level where some strings are valid. We’ll use a set to avoid duplicate strings and a function to check whether a string is valid.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

from collections import deque

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # Function to check if the string is valid
        def isValid(string: str) -> bool:
            count = 0
            for char in string:
                if char == '(':
                    count += 1
                elif char == ')':
                    count -= 1
                    if count < 0:
                        return False
            return count == 0

        # Initialize a queue for BFS and a set to store visited strings
        queue = deque([s])
        visited = set([s])
        found = False
        results = []

        while queue:
            level_size = len(queue)
            current_level = []
            for i in range(level_size):
                current_string = queue.popleft()
                if isValid(current_string):
                    found = True
                    results.append(current_string)
                elif not found:
                    for j in range(len(current_string)):
                        if current_string[j] in '()':
                            new_string = current_string[:j] + current_string[j + 1:]
                            if new_string not in visited:
                                visited.add(new_string)
                                queue.append(new_string)
            if found:
                break

        return results

The function isValid checks whether a given string is a valid expression with balanced parentheses. In the main function, we use a queue to perform a BFS and a set to track visited strings. We stop exploring further levels as soon as we find valid expressions. This ensures that we remove the minimum number of invalid parentheses.

10 Prerequisite LeetCode Problems

This involves depth-first search (DFS) and string manipulation. Here are some simpler problems to prepare for it:

  1. 20. Valid Parentheses: Basic problem to check if a string of parentheses is valid or not.

  2. 32. Longest Valid Parentheses: Understanding how to find the longest valid sequence of parentheses.

  3. 1249. Minimum Remove to Make Valid Parentheses: Helps to understand how to make a string of parentheses valid by removing minimum number of parentheses.

  4. 22. Generate Parentheses: Introduces the concept of generating all possible valid parentheses combinations using DFS.

  5. 678. Valid Parenthesis String: Understand how to check validity of a parentheses string with wildcard characters.

  6. 394. Decode String: Introduces string manipulation and stack usage which is necessary for parentheses problems.

  7. 921. Minimum Add to Make Parentheses Valid: Another problem on making a string of parentheses valid.

  8. 1111. Maximum Nesting Depth of Two Valid Parentheses Strings: Helps to understand the concept of parentheses depth.

  9. 1614. Maximum Nesting Depth of the Parentheses: Another problem to understand the concept of parentheses depth.

  10. 1190. Reverse Substrings Between Each Pair of Parentheses: Complex string manipulation with parentheses which helps in understanding how parentheses can alter string manipulation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def isValid(s):
            stack = []
            for i in range(len(s)):
                if( s[i] == '(' ):
                    stack.append( (i,'(') )
                elif( s[i] == ')' ):
                    if(stack and stack[-1][1] == '('):
                        stack.pop()
                    else:
                        stack.append( (i,')') )         
            return len(stack) == 0, stack


        def dfs( s, left, right):
            visited.add(s)
            if left == 0 and right == 0 and isValid(s)[0]:  res.append(s)
            for i, ch in enumerate(s):
                if ch != '(' and ch != ')': continue    
                if (ch == '(' and left == 0) or (ch == ')' and right == 0): continue    
                if s[:i] + s[i+1:] not in visited:
                    dfs( s[:i] + s[i+1:], left - (ch == '('), right - (ch == ')') )

        stack = isValid(s)[1]
        lc = sum([1 for val in stack if val[1] == "("]) # num of left braces
        rc = len(stack) - lc

        res, visited = [], set()
        dfs(s, lc, rc)
        return res

Problem Classification

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

Example 1:

Input: s = “()())()” Output: ["(())()","()()()"]

Example 2:

Input: s = “(a)())()” Output: ["(a())()","(a)()()"]

Example 3:

Input: s = “)(” Output: [""]

Constraints:

1 <= s.length <= 25 s consists of lowercase English letters and parentheses ‘(’ and ‘)’. There will be at most 20 parentheses in s.

Language Agnostic Coding Drills

  1. Understanding Lists/Arrays and String Manipulation: Familiarize yourself with list operations like appending, popping, and checking if an item exists in the list. Similarly, for strings, focus on string slicing, concatenation and comparison.

  2. Understanding Stacks: Understand how to use a stack data structure to keep track of elements in an ordered way. Specifically, practice using a stack to balance parentheses or brackets.

  3. Recursive Functions (Depth-First Search): This concept is crucial in the code. Depth-first search (DFS) is a fundamental algorithm for searching or traversing tree or graph data structures. Here it is used to recursively explore different combinations of the string by removing parentheses.

  4. Set Data Structure: Understand the use of sets for efficient lookup and keeping track of visited nodes/strings. Sets are used to avoid redundant calculations by storing previously visited strings.

  5. Decision Making in Recursion: Learn how to make decisions during recursion. In this case, it is deciding when to stop the recursion (when no invalid parentheses are left) and when to avoid certain recursive calls (when we have already visited a configuration).

Here is a step by step approach from problem statement to the final solution:

  1. Start with the given string of parentheses.
  2. Use a stack data structure to check the validity of the parentheses string. If the string is valid, return it. If not, keep track of the indices and types of the unbalanced parentheses in the stack.
  3. Start a depth-first search process to remove invalid parentheses. Use the counts of left and right parentheses to keep track of the number of parentheses to be removed.
  4. In each step of the DFS, check the validity of the current string. If it’s valid and there are no parentheses left to remove, add the string to the result list.
  5. Continue the DFS until all combinations have been checked. During this process, avoid visiting the same string more than once by storing visited strings in a set.
  6. After the DFS process, return the result list containing all valid strings with the minimum number of parentheses removed.

Targeted Drills in Python

  1. Understanding Lists/Arrays and String Manipulation:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Lists
my_list = [1, 2, 3]
my_list.append(4) # Appending to list
print(my_list) # Output: [1, 2, 3, 4]

# Strings
my_str = 'hello'
print(my_str[:3]) # Slicing a string, Output: 'hel'
print(my_str + ' world') # Concatenating strings, Output: 'hello world'
print('h' in my_str) # Checking if character is in string, Output: True
  1. Understanding Stacks:
1
2
3
4

# Stacks
stack = []
stack.append('(') # Pushing to stack
stack.pop() # Popping from stack
  1. Recursive Functions (Depth-First Search):
1
2
3
4
5
6
7

# DFS on a binary tree
def dfs(node):
    if node is None:
        return
    print(node.val)
    dfs(node.left)
    dfs(node.right)
  1. Set Data Structure:
1
2
3
4

# Set operations
my_set = set()
my_set.add('hello') # Adding to set
print('hello' in my_set) # Checking if item is in set, Output: True
  1. Decision Making in Recursion:
1
2
3
4
5
6
7

# Making decisions in a recursive function
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
print(factorial(5)) # Output: 120

For the problem-specific drill, you might want to specifically practice the concept of using a stack for parentheses balancing. Here is a simple Python code for that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def is_balanced(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack or stack[-1] != '(':
                return False
            stack.pop()
    return len(stack) == 0

print(is_balanced('(())')) # Output: True
print(is_balanced('(()')) # Output: False