Problem Statement
Minimum Remove to Make Valid Parentheses
You are given a string s made of '(', ')', and lowercase letters. Some of the parentheses do not pair up correctly. Your job is to delete as few parentheses as possible so that the ones left over are balanced. Balanced means every open parenthesis '(' has a later ')' that closes it, and every ')' has an earlier '(' that opened it, with no leftovers. The tool that fits this perfectly is a stack. A stack is like a pile of plates: you add a plate on top, and when you take one, you take the top one first. The last thing you put on is the first thing you take off (this is called last in, first out). Here is why a stack fits: when we read a ')', the '(' it should match is the most recent unmatched '(' we have seen, which is exactly the one sitting on top of the pile. We use the stack to remember the positions (indices) of '(' characters that have not been closed yet. We make two simple passes: first we figure out which parentheses are unmatched, then we build the answer by leaving those out.
Signals to notice
Brute force first
Try removing every subset and check validity. Exponential. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
The key insight
Stack of indices: push '(' indices. On ')': if stack has '(', pop (matched). Else mark this ')' for removal. After processing, remaining '(' on stack are also removed. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on s="lee(t(c)o)de)"
init: stack=[], to_remove={}
i=3 '(': push → stack=[3]
i=5 '(': push → stack=[3,5]
i=7 ')': stack nonempty → pop → stack=[3]
i=9 ')': stack nonempty → pop → stack=[]
i=12 ')': stack empty → to_remove={12}
end of loop: to_remove.update(stack=[]) → to_remove={12}
build: drop index 12 → return "lee(t(c)o)de"What must stay true
The stack tracks unmatched '(' indices. Unmatched ')' are detected immediately. At the end, both types of unmatched parentheses are removed. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
stack = []; to_remove = set()
for i, ch in s:
if ch == '(': stack.push(i)
elif ch == ')': pop if stack else to_remove.add(i)
to_remove |= stack # leftover '(' unmatched
return chars of s where i not in to_removePseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Only removing unmatched ')' — you must also remove unmatched '(' that remain on the stack after processing the entire string. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.