Course4all
Join us on telegram
Home/dsa/Backtracking/Remove Invalid Parentheses

Remove Invalid Parentheses

Master this topic with zero to advance depth.

Remove Invalid Parentheses

Minimal Removal

To make a string valid with minimal removals, we first calculate the number of misplaced open ( and closed ) parentheses.

BFS vs. Backtracking

  • BFS: Guarantees finding the minimal removal level first. We remove one paren at a time and check validity.
  • Backtracking: More memory efficient. We use the pre-calculated remOpen and remClosed to limit our search space and prune invalid branches early.

Remove the minimum number of invalid parentheses to make the input string valid. Includes visual removal tree.

Hard

Examples

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

Level I: Backtracking with Pruning

Intuition

Count how many '(' and ')' need to be removed, then use DFS to try all removal combinations.

Calculate remL and remR. In DFS, for each character: 1. If it's '(' and remL > 0, try removing it. 2. If it's ')' and remR > 0, try removing it. 3. Always try keeping it if valid.

⏱ O(2^N)💾 O(N)

Detailed Dry Run

s="())", remL=0, remR=1 1. Index 0 '(': Keep it. (L=1, R=0) 2. Index 1 ')': - Remove: DFS(idx 2, L=1, R=0) -> "()" Valid! - Keep: (L=1, R=1) 3. Index 2 ')': - Remove: DFS(idx 3, L=1, R=1) -> "()" Valid!
java
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int remL = 0, remR = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') remL++;
            else if (c == ')') {
                if (remL > 0) remL--;
                else remR++;
            }
        }
        Set<String> res = new HashSet<>();
        backtrack(s, 0, 0, 0, remL, remR, new StringBuilder(), res);
        return new ArrayList<>(res);
    }
    private void backtrack(String s, int idx, int leftCount, int rightCount, int remL, int remR, StringBuilder path, Set<String> res) {
        if (idx == s.length()) {
            if (remL == 0 && remR == 0) res.add(path.toString());
            return;
        }
        char c = s.charAt(idx);
        int len = path.length();
        if (c == '(' && remL > 0) backtrack(s, idx + 1, leftCount, rightCount, remL - 1, remR, path, res);
        if (c == ')' && remR > 0) backtrack(s, idx + 1, leftCount, rightCount, remL, remR - 1, path, res);
        
        path.append(c);
        if (c != '(' && c != ')') backtrack(s, idx + 1, leftCount, rightCount, remL, remR, path, res);
        else if (c == '(') backtrack(s, idx + 1, leftCount + 1, rightCount, remL, remR, path, res);
        else if (leftCount > rightCount) backtrack(s, idx + 1, leftCount, rightCount + 1, remL, remR, path, res);
        path.setLength(len);
    }
}
← Previous QuestionSudoku Solver (Advanced)
Next Question →Beautiful Arrangement