Minimum Remove to Make Valid Parentheses
Understanding the Problem
We have a string that contains lowercase letters and parentheses. Some of those parentheses might be unmatched, meaning there's a ( without a corresponding ), or vice versa. We need to remove the minimum number of parentheses to make every remaining parenthesis properly matched.
Lowercase letters never cause problems. They can stay no matter what. The only characters we would ever remove are ( or ), and we want to remove as few as possible.
So the real question is which specific parentheses are unmatched. If we can identify exactly those, we remove them and keep everything else. A closing parenthesis ) is unmatched when no open ( precedes it to pair with, and an opening parenthesis ( is unmatched when it is left over after every ) has been paired.
Key Constraints:
1 <= s.length <= 10^5-- With n up to 100,000, an O(n^2) approach risks timing out. We want a linear scan.s[i]is either'(',')', or lowercase English letter -- Only two characters can ever be removed. Letters are always kept.
Approach 1: Stack to Track Indices
Intuition
A stack matches parentheses by tracking which open ( is still waiting for a partner. Scan the string from left to right. When the character is (, push its index onto the stack. When it is ), look at the stack: if it holds an index, pop it (this ) pairs with that (); if the stack is empty, this ) has no ( before it, so it is unmatched and must be removed.
After the scan, any indices still on the stack are ( characters that never found a ), so they are unmatched too.
The stack gives us the indices of every character to remove. We collect them into a set, then build the final string from every character whose index is not in that set.
Algorithm
- Initialize an empty stack and an empty set called
indicesToRemove. - Iterate through the string character by character:
- If the character is
(, push its index onto the stack. - If the character is
): - If the stack is not empty, pop the top (a matched pair).
- If the stack is empty, add this index to
indicesToRemove(unmatched)). - After the loop, pop all remaining indices from the stack into
indicesToRemove(unmatched(). - Build the result string by including characters whose indices are not in
indicesToRemove.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We scan the string once to identify unmatched parentheses, then scan it again to build the result. Each stack and set operation is O(1).
- Space Complexity: O(n). The stack can hold up to n/2 indices. The set can also hold up to n indices. The result string is O(n).
This works, but the stack and hash set are not strictly necessary. The next approach replaces both with a single counter and two passes over the string.
Approach 2: Two-Pass with Counter (Optimal)
Intuition
Unmatched parentheses come in two forms, and each can be caught with a single integer counter instead of a stack:
- Unmatched
): A)is unmatched when there is no preceding unmatched(to pair with. Scanning left to right, keep a counter of how many(are open. When the counter is zero and we see a), it is unmatched.
- Unmatched
(: A(is unmatched when no)follows it before the end of the string. Scanning right to left, keep a counter of how many)are open. When that counter is zero and we see a(, it is unmatched.
So we make two passes. The first pass (left to right) removes every unmatched ). The second pass (right to left) removes every unmatched (. After both passes, every remaining parenthesis is matched. A counter holds a single number per pass, so the only extra space is the output itself.
The counter is a stack with only its height retained. We never need to know which ( a given ) pairs with, only whether one is available, so a count is enough. When openCount is zero and a ) arrives, no open ( exists to its left, so removing that ) is forced, never a choice.
Two directions are required because the two failure modes are not symmetric within one pass. A left-to-right scan cannot tell whether an open ( will eventually be closed, so it cannot safely remove a (. After pass one, every ) is already paired, so the leftover unmatched parentheses are all (, and the right-to-left scan removes exactly those. Each removal is forced, so the total removed is the minimum possible.
Algorithm
- First pass (left to right): Remove unmatched
). - Initialize
openCount = 0. - For each character in the string:
- If it's
(, incrementopenCount. - If it's
): ifopenCount > 0, decrementopenCount(matched pair). IfopenCount == 0, skip this character (unmatched)). - If it's a letter, keep it.
- Collect the surviving characters into an intermediate string.
- Second pass (right to left): Remove unmatched
(. - Initialize
closeCount = 0. - For each character in the intermediate string (from right to left):
- If it's
), incrementcloseCount. - If it's
(: ifcloseCount > 0, decrementcloseCount(matched pair). IfcloseCount == 0, skip this character (unmatched(). - If it's a letter, keep it.
- Collect the surviving characters and reverse.
- Return the final string.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Two passes through the string, each doing O(1) work per character. The final reverse is also O(n).
- Space Complexity: O(n). We store the intermediate string and the result, each up to length n. The counter variables use O(1) auxiliary space.