Course4all

Remove Invalid Parentheses

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Backtracking.

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);
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSudoku Solver (Advanced)
Next Question →Beautiful Arrangement