Problem

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

Return all the possible results. You may return the answer in any order.

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

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Solution

Method 1 - BFS 🥈

Using BFS, the approach involves generating all possible states by removing one ( or ) at a time. We check if these states are valid, and if valid states are found at the current level, they are added to the final result list, and the search stops. Otherwise, the states are added to the queue and the search continues to the next level.

Using BFS guarantees that the number of parentheses that need to be removed is minimal, also no recursion call is needed in BFS.

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
42
43
44
45
46
47
48

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();

        if (s == null) return res;

        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        queue.add(s);
        visited.add(s);

        boolean found = false;

        while (!queue.isEmpty()) {
            s = queue.poll();

            if (isValid(s)) {
                res.add(s);
                found = true;
            }

            if (found) continue;

            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;

                String t = s.substring(0, i) + s.substring(i + 1);

                if (!visited.contains(t)) {
                    queue.add(t);
                    visited.add(t);
                }
            }
        }

        return res;
    }

    private boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') count++;
            if (c == ')' && count-- == 0) return false;
        }
        return count == 0;
    }
}
 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
42
43
44
45

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        res = []

        if s is None:
            return res

        visited = set()
        queue = deque([s])
        visited.add(s)
        
        found = False

        while queue:
            s = queue.popleft()

            if self.isValid(s):
                res.append(s)
                found = True

            if found:
                continue

            for i in range(len(s)):
                if s[i] != '(' and s[i] != ')':
                    continue

                t = s[:i] + s[i+1:]

                if t not in visited:
                    queue.append(t)
                    visited.add(t)

        return res

    def isValid(self, s: str) -> bool:
        count = 0
        for c in s:
            if c == '(':
                count += 1
            if c == ')':
                count -= 1
                if count < 0:
                    return False
        return count == 0

Complexity

In BFS, we process the states level by level. In the worst case, we might need to process all levels. Let’s analyze the time complexity level by level.

On the first level, there’s only one string which is the input string s of length n. Checking its validity takes O(n) time. On the second level, we generate C(n, n-1) new strings by removing one parenthesis from the first level, each of length n-1. Validating each string takes O(n-1) time, so total time complexity for this level is (n-1) * C(n, n-1). For the third level, it’s (n-2) * C(n, n-2). Continuing this pattern, we get:

1

T(n) = n X C(n, n) + (n-1) X C(n, n-1) + ... + 1 X C(n, 1) = n X 2^{(n-1)}

Method 2 - Backtracking + DFS

Another approach we can think of is following:

  1. Counting the number of invalid characters that need to be removed from the string to make it valid.
  2. Using DFS/backtracking to generate all possible substrings by removing the invalid characters, similar to the BFS solution, and exploring each level until all necessary characters have been removed.
  3. We can create a map of <String, Boolean> for memoization to store whether a string has already been processed and if it is valid.

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
42
43
44
45
46
47
48

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        Set<String> set = new HashSet<>();
        
        int minBracket = getInvalidBracketCount(s);
        helper(s, minBracket, set, ans);
        
        return ans;
    }

    public void helper(String s, int minBracket, Set<String> set, List<String> ans) {
        if (set.contains(s)) return;
        set.add(s);

        if (minBracket == 0) {
            int remove = getInvalidBracketCount(s);
            if (remove == 0) {
                ans.add(s);
            }
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '(' && s.charAt(i) != ')') {
                continue;
            }
            String t = s.substring(0, i) + s.substring(i + 1);
            helper(t, minBracket - 1, set, ans);
        }
    }

    public int getInvalidBracketCount(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        return stack.size();
    }
}
 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

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        ans = []
        visited = set()
        
        min_bracket = self.get_invalid_bracket_count(s)
        self.helper(s, min_bracket, visited, ans)
        
        return ans

    def helper(self, s: str, min_bracket: int, visited: Set[str], ans: List[str]) -> None:
        if s in visited:
            return
        visited.add(s)
        
        if min_bracket == 0:
            if self.get_invalid_bracket_count(s) == 0:
                ans.append(s)
            return
        
        for i in range(len(s)):
            if s[i] not in ('(', ')'):
                continue
            t = s[:i] + s[i+1:]
            self.helper(t, min_bracket - 1, visited, ans)

    def get_invalid_bracket_count(self, s: str) -> int:
        stack = []
        for c in s:
            if c == '(':
                stack.append(c)
            elif c == ')':
                if stack and stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(c)
        return len(stack)

Complexity

  • ⏰ Time complexity: O(n * 2^n), where n is the length of the string. In the worst case, we may need to explore all possible states by removing invalid parentheses one by one. The time complexity is exponential and can be approximated as O(2^n)
  • 🧺 Space complexity: O(2^n) due to the storage of all possible states in the visited set and the recursive call stack.