0550HardStringBacktrackingBreadth-First Search

Repairing a Template's Brackets

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A small template language allows lowercase letters and the two round brackets. A string counts as balanced when every ( is closed by a ) somewhere after it and every ) closes a ( somewhere before it. The empty string is balanced, and letters never affect whether a string is balanced.

The linter is handed s and must delete as few brackets as possible so that what remains is balanced. Letters are never deleted.

Return every distinct string that can be produced by deleting that smallest number of brackets. The order of the returned strings does not matter, but no string may appear twice.

Examples

Example 1

Input: s = "a(b)c)d"
Output: ["a(b)cd", "a(bc)d"]

One closing bracket has nothing to close, so one deletion is enough. Dropping the bracket at position 3 leaves "a(bc)d" and dropping the one at position 5 leaves "a(b)cd"; both are balanced, so both are returned.

Example 2

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

The opening bracket is never closed, so it must go, and the letters stay put, leaving "fg".

Example 3

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

One of the two opening brackets has to go. Deleting either of them leaves the same string "(h)", and it is only listed once.

Constraints

1 <= s.length <= 25
s contains only lowercase English letters and the characters '(' and ')'.
s holds at most 20 brackets.

The values you return may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def remove_invalid_parentheses(s: str) -> list[str]:

Java

public List<String> removeInvalidParentheses(String s)

The intended approach

Time O(2^b * n) in the worst case, where b is the number of brackets, since each bracket is either kept or dropped and finishing a branch costs O(n).Space O(n) for the recursion and the partial string, plus the returned set of answers.

One scan settles the deletion budget. Walk the string counting unclosed `(`, and each `)` either cancels one of them or is itself unmatched; the unclosed opens and the unmatched closes are exactly how many of each kind must go, and no smaller number can work. Then backtrack through the string with that budget: a letter is always kept, a bracket may be dropped while budget of its kind remains, and a `)` may only be kept while some `(` is still open. A completed walk that spent the whole budget and left nothing open is a valid answer, collected into a set so repeated results collapse. Two cheap cut-offs keep the search in hand: stop when the remaining budget exceeds the characters left, and stop when more brackets are open than there are characters left to close them.

Pythonentry point: remove_invalid_parentheses

def remove_invalid_parentheses(s):
    # First count how many brackets have to go: scan once, cancelling each ')'
    # against a waiting '(', and whatever is left over on each side is exactly
    # the number of deletions of that kind. Then a backtracking walk keeps or
    # drops each bracket, spending only that many deletions, so every string it
    # completes uses the smallest possible number.
    n = len(s)
    drop_open = 0
    drop_close = 0
    for ch in s:
        if ch == "(":
            drop_open += 1
        elif ch == ")":
            if drop_open:
                drop_open -= 1
            else:
                drop_close += 1
    found = set()

    def walk(i, built, waiting, left_open, left_close):
        if left_open + left_close > n - i:
            return
        if waiting > n - i:
            return
        if i == n:
            if left_open == 0 and left_close == 0 and waiting == 0:
                found.add("".join(built))
            return
        ch = s[i]
        if ch == "(":
            if left_open > 0:
                walk(i + 1, built, waiting, left_open - 1, left_close)
            built.append(ch)
            walk(i + 1, built, waiting + 1, left_open, left_close)
            built.pop()
        elif ch == ")":
            if left_close > 0:
                walk(i + 1, built, waiting, left_open, left_close - 1)
            if waiting > 0:
                built.append(ch)
                walk(i + 1, built, waiting - 1, left_open, left_close)
                built.pop()
        else:
            built.append(ch)
            walk(i + 1, built, waiting, left_open, left_close)
            built.pop()

    walk(0, [], 0, drop_open, drop_close)
    return list(found)

The obvious version

Search by number of deletions. Start with the single original string; if any string in the current batch is balanced, return all the balanced ones from that batch. Otherwise build the next batch by deleting one bracket from each string in every possible position, holding them in a set so repeats collapse, and try again. The first batch containing a balanced string is by construction the one that used the fewest deletions.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_remove_invalid_parentheses(s):
    def balanced(text):
        depth = 0
        for ch in text:
            if ch == "(":
                depth += 1
            elif ch == ")":
                depth -= 1
                if depth < 0:
                    return False
        return depth == 0

    level = {s}
    while level:
        keep = [t for t in level if balanced(t)]
        if keep:
            return keep
        nxt = set()
        for text in level:
            for i, ch in enumerate(text):
                if ch == "(" or ch == ")":
                    nxt.add(text[:i] + text[i + 1:])
        level = nxt
    return [""]

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in