Minimum Remove to Make Valid Parentheses
Minimum Remove to Make Valid Parentheses: delete the fewest parentheses possible so the result is valid, keeping all letters. Any valid answer is accepted.
- 1 <= s.length <= 10⁵
- s[i] is either '(' , ')' , or a lowercase English letter.
Intuition
Only two kinds of parenthesis can ever be wrong: a ) that arrives with no open partner, and a ( that is still unmatched when the string ends. Find exactly those and delete only them. Every other bracket is part of a legitimate pair, so removing anything else would be more than the minimum.
Balanced-delimiter validity is always a stack question, and the 'minimum deletions' twist just means recording the offenders instead of returning false at the first one. The same identify-the-doomed-then-rebuild shape appears in Remove Invalid Parentheses and Valid Parenthesis String.
Approach
Before reading on: name the only two situations in which a parenthesis can never be part of a valid pair. Convince yourself that deleting precisely those is both necessary and enough. Aim for O(n).
Identify the two failure modes
Scan left to right tracking indices of unmatched ( on a stack. When a ) appears and the stack is non-empty, it pairs with the most recent ( — pop and both are safe. When a ) appears and the stack is empty, nothing can ever match it, because any later ( opens after it. That index is doomed. When the scan finishes, whatever remains on the stack is a set of ( that never found a partner, and those are doomed too. These are the only two ways a string can be invalid.
Why deleting exactly those is minimal
Each doomed index must be removed — a stray ) cannot be fixed by deleting anything else, and neither can a stray (. So the doomed set is a lower bound on the number of deletions. It is also sufficient: after removing them, every surviving ( has a matching ) after it and vice versa, so the string is valid. A set that is both necessary and sufficient is exactly the minimum. Letters are never touched, since they cannot affect validity.
Rebuild in one pass
Collect the doomed indices into a set, then build the answer by appending every character whose index is not in it. Using a set makes each membership test O(1), so the rebuild is O(n). Total cost is two linear passes and O(n) auxiliary space for the stack and the result. Building a new string is cleaner than repeated deletions, which would be O(n²) because each removal shifts the tail.
Solution & live demo
Common pitfalls
Using a counter but losing positions
open_count = 0
for ch in s:
if ch == '(': open_count += 1stack.append(i) # store the index
A counter can tell you how many brackets are unmatched but not which, and the answer requires deleting specific positions. Push indices so the leftovers can be blanked at the end.
Deleting from the string while scanning
s = s[:i] + s[i+1:]
chars[i] = "" # blank it, join later
Every deletion re-indexes the remaining characters, so the loop variable no longer matches the intended position and the scan skips characters. It is also O(n²). Mark first, rebuild once.
Forgetting the leftovers on the stack
# handle only the stray ')' cases return ''.join(chars)
for i in stack:
chars[i] = ''
return ''.join(chars)Unmatched ( are only discovered when the scan ends. Skipping that final loop leaves "(a" unchanged and returns an invalid string.
Edge cases
The stack empties naturally and no index is marked, so the string is returned unchanged.
No parentheses are seen at all; the result equals the input.
Both ) are marked on arrival and both ( are marked at the end, leaving an empty string.
The stack pairs innermost-first, so all four brackets survive.
Two indices remain on the stack and are removed, leaving "ab".