Remove Invalid Parentheses

Remove Invalid Parentheses asks for the fewest deletions that make a string of parentheses valid — and every distinct result that achieves that minimum. The "fewest" requirement is the tell: when a problem wants the shortest path or smallest number of edits, BFS is the natural fit.

The slow way first

You could try every possible subset of characters to delete, validate each, and keep the shortest valid ones. With n characters there are 2ⁿ subsets — exponential, and you would still have to figure out which valid results used the fewest deletions. We want something that finds the minimum first, without exploring deeper than necessary.

The question to ask: can I explore by number of deletions, smallest first, and stop the moment I succeed? That is exactly what breadth-first search does.

The idea: BFS by number of removals

Treat each string as a node in a graph. Its neighbors are all the strings you get by deleting one character. Level 0 is the original string (zero removals), level 1 is every string with one removal, level 2 with two, and so on. BFS scans an entire level before going deeper, so the first level that contains any valid string holds all the minimum-removal answers — collect every valid string on that level and stop.

The key insight: because BFS reaches shorter-removal strings before longer-removal ones, the first valid level is guaranteed minimal. We collect all valid strings on it (there can be several) and never descend further.

Walk through it

Step through the animation. Level 0 is "()())" — scanning its balance dips to −1, so it is invalid. Level 1 deletes one character at every position. Two distinct candidates, "()()" and "(())", are valid, so they are the answer. We dedupe with a seen set and stop without touching level 2.

Pseudocode

if s is already valid: return [s]
queue = [s], seen = {s}
while queue is not empty:
    found = []
    for each string cur in queue:
        for each index i in cur:
            cand = cur with character i removed
            if cand is valid:
                add cand to found
            else if cand not seen before:
                mark cand seen, push it to the next level
    if found is non-empty:
        return the distinct strings in found   # first valid level = minimum removals
    advance queue to the next level

The Python solution

def remove_invalid(s):
    def valid(t):
        bal = 0
        for ch in t:
            if ch == "(": bal += 1
            elif ch == ")": bal -= 1
            if bal < 0: return False
        return bal == 0
    queue, seen = [s], {s}
    while queue:
        found, nxt = [], []
        for cur in queue:
            for i in range(len(cur)):
                cand = cur[:i] + cur[i+1:]
                if valid(cand):
                    found.append(cand)
                elif cand not in seen:
                    seen.add(cand); nxt.append(cand)
        if found: return list(set(found))
        queue = nxt
    return [""]

• valid(t) sweeps the string tracking bal — it returns False the instant balance goes negative (a close with no matching open) and requires it to end at exactly 0.
• queue holds the current BFS level; seen prevents re-processing a string we already generated.
• The inner loops generate every one-character-removal neighbor of each string on the level.
• A candidate that is valid goes into found; an unseen invalid one is queued for the next level.
• if found: is the stopping rule — the first level with any valid string returns list(set(found)) so duplicates collapse. We never expand a deeper level.

Complexity

Worst case is still exponential — that is inherent to returning all answers — but BFS stops at the shallowest valid level, so in practice it explores far fewer strings than enumerating every subset. The seen set keeps the queue from blowing up with duplicate strings.

When this pattern shows up

Practice