0362MediumStringStack

Trim the Unpaired Brackets

Tracked in this browser only

Trains the technique from

LeetCode 1249Minimum Remove to Make Valid Parentheses

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 macro language writes each step as a string s of lowercase letters and the round brackets ( and ).

Brackets are meant to nest. Reading s from left to right, a ) closes the nearest ( to its left that nothing has closed yet. A step is well formed when every bracket ends up with a partner under that rule.

The linter repairs a step that is not well formed by deleting brackets, and it deletes as few as it can. Which ones go is pinned down: pair the brackets up by the nearest-open rule above, then delete every ) that found no open bracket to close and every ( that never got closed. Letters are never deleted, and every surviving character keeps its original position relative to the others.

Return the string the linter produces.

Examples

Example 1

Input: s = "fo)o(bar)"
Output: "foo(bar)"

The `)` at index 2 has no open bracket waiting to its left, so it is deleted. The `(` at index 4 is closed by the `)` at index 8, so that pair and every letter stay.

Example 2

Input: s = "a(b(c)"
Output: "ab(c)"

The `)` at index 5 closes the nearest unclosed open bracket to its left, which is the `(` at index 3. The `(` at index 1 is then left without a partner, so that is the character deleted.

Example 3

Input: s = "(a)((b"
Output: "(a)b"

The `)` at index 2 closes the `(` at index 0. The open brackets at indices 3 and 4 are never closed, so both are deleted.

Example 4

Input: s = "mix"
Output: "mix"

There are no brackets to pair, so nothing is deleted.

Constraints

1 <= s.length <= 10^5
s[i] is '(' , ')', or a lowercase English letter.

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 min_remove_to_make_valid(s: str) -> str:

Java

public String minRemoveToMakeValid(String s)

The intended approach

Time O(n)Space O(n) for the stack of pending positions and the returned string

Sweep left to right keeping a stack of the positions of open brackets that are still waiting. A closing bracket pops that stack when it can, otherwise it had nothing to close and is marked for deletion. Whatever positions remain on the stack at the end are open brackets that were never closed, so they are marked too, and the answer is the input with the marked positions skipped.

Pythonentry point: min_remove_to_make_valid

def min_remove_to_make_valid(s):
    # One pass with a stack of open-bracket positions. O(n) time,
    # O(n) space for the stack plus the returned string.
    opens = []
    drop = set()
    for i, ch in enumerate(s):
        if ch == "(":
            opens.append(i)
        elif ch == ")":
            if opens:
                opens.pop()
            else:
                drop.add(i)
    drop.update(opens)
    return "".join(ch for i, ch in enumerate(s) if i not in drop)

The obvious version

For each closing bracket walk left one character at a time until an open bracket that has not been claimed yet turns up, and claim it; mark the closing bracket if the walk falls off the front. Any open bracket left unclaimed at the end is marked too.

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_min_remove_to_make_valid(s):
    n = len(s)
    taken = [False] * n
    drop = [False] * n
    for j in range(n):
        if s[j] != ")":
            continue
        k = j - 1
        while k >= 0 and not (s[k] == "(" and not taken[k]):
            k -= 1
        if k < 0:
            drop[j] = True
        else:
            taken[k] = True
    for i in range(n):
        if s[i] == "(" and not taken[i]:
            drop[i] = True
    return "".join(s[i] for i in range(n) if not drop[i])

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
4 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