1249. Minimum Remove to Make Valid Parentheses

1249

MediumStack and Expression ProcessingStackIndex stack for unmatched brackets

Minimum Remove to Make Valid Parentheses

Given a string s of '(' , ')' and lowercase English letters, remove the minimum number of parentheses ('(' or ')') so that the resulting string is valid and return any such result. A string is valid if it is empty, contains only letters, or every parenthesis is properly matched. Letters are never removed.

Open official problem prompt ↗

In plain English

Produce a valid string by deleting as few parentheses as possible while leaving letters and their positions intact.

Picture it like this

Like proofreading brackets in an equation: cross out every stray closing bracket that opens nothing, then cross out every opening bracket that was never closed.

Example

Input: s = "a)b(c)d"
Output: "ab(c)d"
Why: The leading ')' at index 1 has no matching '(', so removing just that one closing parenthesis makes the string valid while keeping all letters and the matched pair.

Constraints

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

Pattern lesson

See the pattern, then code

Index stack for unmatched brackets

↗

Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. A ')' is invalid the moment it appears with no open '(' to match, so mark it immediately; any '(' still unmatched at the end is invalid, so mark those too, and delete exactly the marked positions.

New words, made simpleKnow these before the algorithm

Unmatched close: A ')' that appears with no available unmatched '(' before it.
Index stack: A stack storing the positions of open parentheses so unmatched ones can be located and blanked later.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Repeated scanning removal

Rescanning after each deletion is quadratic for n up to 10^5.

Repeatedly find and delete an unmatched bracket until valid.

Time O(n^2)Space O(n)

Best choiceOne-pass index stack

Two linear passes identify exactly the invalid brackets and remove only those.

Blank unmatched ')' during the scan and blank leftover '(' indices afterward.

Time O(n)Space O(n)

The rule we keep true

Invariant

The stack holds the indices of all '(' seen so far that are still waiting for a match; anything blanked is provably unmatched and must be removed.

Why this is correct

Reasoning

Removing only brackets that can never be matched is necessary, and it is sufficient because after removal every remaining ')' had a matching '(' at pop time and every remaining '(' was matched by a later ')'. Since we delete exactly the unmatched brackets and no letters, the count is minimal.

The algorithm in three movesSay these aloud before coding

1Convert the string to a mutable list of characters

index1 ')' no open -> blank

2Push each '(' index onto a stack

index3 '(' -> stack=[3]

3On a ')', pop a matching '(' index if available, otherwise blank out this ')'

index5 ')' -> pop 3, matched

4After the scan, blank out every index left on the stack (unmatched '(')

5Join the surviving characters

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read'a'

2 · AskBracket?

3 · Update statechars unchanged, stack=[]

4 · ResultLetter, ignore

Key takeaway

The unmatched ')' at index 1 is removed while the matched pair (index 3, 5) stays.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Mutable buffer
A list of characters lets us blank positions in place before joining.
2
Lines 6-11First pass
Push '(' indices, match ')' against them, and blank any ')' with no available match.
3
Lines 12-13Second pass
Every index left on the stack is an unmatched '(' and gets blanked.
4
Lines 14Rebuild
Joining skips the blanked slots, yielding a valid string.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

No parentheses at all, e.g. "abc" returns unchanged
Only unmatched brackets, e.g. "))((" returns ""
Already valid, e.g. "(a(b)c)" returns unchanged
Nested and adjacent groups, e.g. "(a(b(c)d)e)"

Common beginner mistakes

Removing letters or shifting their positions
Forgetting the second pass that clears leftover unmatched '(' indices
Using string concatenation in a loop instead of a mutable list, causing O(n^2) behavior
Confusing this with problem 921, which only counts insertions instead of returning a fixed string

Check your understanding

Why does blanking exactly the unmatched brackets guarantee a minimum number of removals?

Minimum Remove to Make Valid Parentheses

Minimum Remove to Make Valid Parentheses

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Stack and Expression Processing