Minimum Remove to Make Valid Parentheses
Problem
Given a string s containing parentheses and lowercase English letters, return a string after removing the minimum number of parentheses to make the input string valid. A string is valid if parentheses are balanced and properly closed.
- 1 ≤ s.length ≤ 10⁵
- s[i] is either '(', ')', or a lowercase English letter.
Example
s = "a)b(c)d""ab(c)d"Walk through the string from left to right: Index 0: 'a' -> not a parenthesis, keep it. Index 1: ')' -> the stack is empty, so there is no matching '('. Mark this ')' for removal by setting s[1] = "". Index 2: 'b' -> keep it. Index 3: '(' -> push index 3 onto the stack. Index 4: 'c' -> keep it. Index 5: ')' -> the stack is not empty, so we pop 3 from the stack and treat this as a matched pair. Keep this ')'. Index 6: 'd' -> keep it. After this pass, any indices left in the stack would be unmatched '(' positions (none in this example). We then mark those for removal as well. Finally, we join the characters that were not cleared out, which gives "ab(c)d", a valid parentheses string with the minimum removals.
Approach
Straightforward Solution
A brute-force approach might try all subsets of characters to find the minimal removal that yields a valid string, which is exponential and infeasible for large inputs.
Core Observation
A valid parentheses string requires every '(' to be matched with a corresponding ')' in the correct order. Unmatched parentheses must be removed to achieve validity.
Path to Optimal
The key insight is to use a stack to track indices of unmatched '(' characters. When encountering a ')', if the stack is empty, this ')' is unmatched and must be removed. Otherwise, pop from the stack to match the pair. After processing the entire string, any indices left in the stack correspond to unmatched '(' that must be removed. This approach ensures minimal removals in a single pass plus a cleanup pass.
Optimal Approach
Convert the string to a list for in-place edits. Iterate through the list, pushing indices of '(' onto a stack. For each ')', pop from the stack if possible; otherwise, mark the ')' for removal by setting it to an empty string. After the iteration, remove all '(' indices remaining in the stack by setting those positions to empty strings. Finally, join the list into a string and return it.
Time
O(n)
The algorithm makes a single pass through the string to identify invalid parentheses and a second pass to remove unmatched openings, each operation being O(1) per character, resulting in O(n) total time.
Space
O(n)
The stack can hold up to O(n) indices in the worst case (all '(' characters). The string is converted to a list of characters, which is O(n) auxiliary space excluding the input and output.
Pattern Spotlight
Stack (Parentheses Matching)
Use a stack to track indices of unmatched opening parentheses. Unmatched closing parentheses are identified immediately and removed, and any remaining unmatched opening parentheses are removed after processing, ensuring minimal removals for validity.
Solution
| 1 | class Solution:
|
| 2 | def minRemoveToMakeValid(self, s: str) -> str:
|
| 3 | s = list(s)
|
| 4 | stack = []
|
| 5 | for i, c in enumerate(s):
|
| 6 | if c == '(':
|
| 7 | stack.append(i)
|
| 8 | elif c == ')':
|
| 9 | if stack:
|
| 10 | stack.pop()
|
| 11 | else:
|
| 12 | s[i] = ''
|
| 13 |
|
| 14 | while stack:
|
| 15 | s[stack.pop()] = ''
|
| 16 | return ''.join(s) |
Step-by-Step Solution
Convert String to List and Initialize Stack for Tracking
| 3 | s = list(s)
|
| 4 | stack = []
|
Objective
To prepare the input for in-place modifications and set up a data structure to track unmatched opening parentheses indices.
Key Insight
Strings in many languages are immutable, so converting to a list allows marking invalid characters by replacing them with empty strings without rebuilding the string repeatedly. The stack stores indices of '(' characters, enabling efficient matching with ')' characters during iteration.
Interview Quick-Check
Core Logic
Converting the string to a list allows O(1) time marking of invalid characters, avoiding costly string concatenations.
State & Boundaries
The stack holds indices of '(' characters that are unmatched so far.
Common Pitfalls & Bugs
Forgetting to convert the string to a mutable structure leads to inefficient or incorrect removal of characters.
Iterate Through Characters to Identify Invalid Parentheses
| 5 | for i, c in enumerate(s):
|
| 6 | if c == '(':
|
| 7 | stack.append(i)
|
| 8 | elif c == ')':
|
| 9 | if stack:
|
| 10 | stack.pop()
|
| 11 | else:
|
| 12 | s[i] = ''
|
Objective
To scan the string and use the stack to match parentheses, marking unmatched closing parentheses for removal.
Key Insight
When encountering '(', push its index onto the stack to await a matching ')'. When encountering ')', if the stack is not empty, pop to match; otherwise, mark the ')' as invalid by replacing it with an empty string. This ensures that unmatched ')' are removed immediately, and unmatched '(' remain on the stack for later removal.
Interview Quick-Check
Core Logic
The stack-based matching ensures that every ')' is matched with the most recent unmatched '(', preserving correct nesting and order.
State & Boundaries
If the stack is empty when encountering ')', it is unmatched and must be removed.
Common Pitfalls & Bugs
Failing to check if the stack is empty before popping leads to errors or incorrect matches.
Remove Remaining Unmatched Opening Parentheses and Rebuild String
| 14 | while stack:
|
| 15 | s[stack.pop()] = ''
|
| 16 | return ''.join(s) |
Objective
To remove all unmatched '(' characters left on the stack and return the valid string.
Key Insight
After the first pass, any indices left in the stack correspond to '(' without matching ')'. Marking these positions as empty strings removes them. Joining the list back into a string produces the final valid string with minimal removals.
Interview Quick-Check
Core Logic
Removing unmatched '(' after the iteration ensures minimal removals and correctness, as these unmatched openings cannot be paired.
State & Boundaries
The while loop continues until all unmatched '(' indices are removed.
Complexity
Joining the list into a string is O(n), which is efficient given the problem constraints.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
stack.append(i)Push the index of '(' onto the stack.
This line is critical because it records the position of an unmatched '(' to enable correct pairing or removal later, forming the backbone of the stack-based matching algorithm.
if stack:Check if there is an unmatched '(' available to match with the current ')'.
This check is crucial to avoid invalid matches and to identify unmatched ')' that must be removed, preserving correctness.
s[i] = ''Mark the unmatched ')' for removal by replacing it with an empty string.
This line's placement is critical to immediately mark unmatched ')' for removal, ensuring minimal removals and preserving the original string structure for subsequent processing.
s[stack.pop()] = ''Mark the unmatched '(' at the popped index for removal by replacing it with an empty string.
Removing unmatched '(' after the full scan is essential because these openings have no matching closing parentheses, ensuring the final string is valid with minimal removals.
stack = []Initialize an empty stack to store indices of unmatched opening parentheses.
The stack tracks positions of '(' characters that have not yet been matched with a corresponding ')', enabling efficient matching during iteration.
stack.pop()Pop the index of the matched '(' from the stack.
Removing the matched '(' index signifies a successful pairing, maintaining the stack's invariant of unmatched openings.
else:Handle the case where the current ')' is unmatched.
If no matching '(' exists, this ')' must be removed to maintain validity.
while stack:Begin removing unmatched '(' characters remaining in the stack.
After processing the entire string, any '(' indices left in the stack are unmatched and must be removed to achieve validity.
s = list(s)Convert the input string into a list of characters for in-place modification.
Strings are immutable, so converting to a list allows marking invalid parentheses by replacing them with empty strings efficiently without rebuilding the string repeatedly.
if c == '(':Check if the current character is an opening parenthesis '('.
Identifying '(' characters is essential to push their indices onto the stack for future matching.
elif c == ')':Check if the current character is a closing parenthesis ')'.
Identifying ')' characters triggers the matching logic with the stack to determine validity.
return ''.join(s)Join the list of characters into a string and return the valid string.
Joining the list reconstructs the string without the removed parentheses, producing the final valid output.
for i, c in enumerate(s):Begin iterating over the list with index and character.
Enumerating both index and character is necessary to track positions for potential removal and to identify parentheses.
Test Your Understanding
Why is it necessary to remove unmatched opening parentheses after processing the entire string rather than during the initial iteration?
Because unmatched opening parentheses can only be identified after processing all characters; they remain on the stack if no matching closing parenthesis is found later, so they must be removed after the full scan to ensure minimal removals.
Related Problems
Stacks pattern
Don't just read it. Drill it.
Reconstruct Minimum Remove to Make Valid Parentheses from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Minimum Remove to Make Valid Parentheses drill