Remove Invalid Parentheses

Intuition

We want the minimum number of removals, so we explore strings in order of increasing removals — exactly what BFS does. Level 0 is the original string (zero removals); level 1 removes one character; and so on. The first level that produces any valid string is the answer, because going deeper would require more removals.

Algorithm

1Initialise a queue with the original string s and a visited HashSet containing s.
2Poll a string cur from the queue.
3If cur passes the validity check (balanced parentheses), add it to the result and set found=true.
4If found is true, skip generating children — we only want results at this minimum level.
5Otherwise, try removing each character that is "(" or ")" and enqueue unseen results.
6Repeat until the queue is empty; return all collected valid strings.

Example Walkthrough

Input: s = "()())()"

1.Level 0: "()())()" — not valid (unmatched closing paren).
2.Level 1: try removing each "(" or ")" → generates candidates like "(())()" and "()()()".
3."(())()" — valid. "()()()" — valid. Set found=true.
4.Continue draining this BFS level but generate no new children.
5.Return ["(())()", "()()()"].

Output: ["(())()", "()()()"]

Common Pitfalls

•Without the visited HashSet, the same string can be generated exponentially many times from different removal sequences.
•Non-parenthesis characters must be skipped during removal — removing letters changes meaning, not balance.
•Setting found=true stops new children being enqueued but does not stop the current level from being fully drained, ensuring all minimum-removal results are collected.

Remove Invalid Parentheses.java

Java


import java.util.*;

// Approach: BFS level by level, each level removes exactly one parenthesis character.
// At the first level where any valid string is found, collect all valid results from that level and stop going deeper.
// A HashSet tracks visited strings to prune duplicate states.
// Time: O(2^n * n) Space: O(2^n * n)

class Solution {

    public List<String> validParenthesis(String s) {
        List<String> ans = new ArrayList<>();

        if (s == null) {
            return ans;
        }

        Set<String> vis = new HashSet<>();
        Queue<String> q = new ArrayDeque<>();
        q.add(s);
        vis.add(s);
        boolean found = false;

        while (!q.isEmpty()) {
            String cur = q.poll();
            if (check(cur)) {
                ans.add(cur);
                found = true;
            }

            if (found) {
                continue;
            }

            for (int i = 0; i < cur.length(); i++) {

                if (cur.charAt(i) != '(' && cur.charAt(i) != ')') {
                    continue;
                }

                String temp = cur.substring(0, i) + cur.substring(i + 1);
                if (!vis.contains(temp)) {
                    q.add(temp);
                    vis.add(temp);
                }
            }
        }

        return ans;
    }

    private boolean check(String s) {
        int bal = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                bal++;
            } else if (c == ')') {
                bal--;
            }

            if (bal < 0) {
                return false;
            }
        }

        return (bal == 0);

    }
}

Was this solution helpful?