LeetCode 1249 - Minimum Remove to Make Valid Parentheses
The problem is asking us to process a string containing lowercase letters and parentheses, and remove the minimum number of parentheses so that the remaining string is valid.
Difficulty: 🟡 Medium
Topics: String, Stack
Solution
Problem Understanding
The problem is asking us to process a string containing lowercase letters and parentheses, and remove the minimum number of parentheses so that the remaining string is valid. A valid string is defined by the usual rules of parentheses: every opening parenthesis '(' must have a corresponding closing parenthesis ')', and parentheses must be properly nested. The input string can be large, up to 100,000 characters, and it may contain multiple misplaced or extra parentheses. The output is any valid string formed by removing the fewest parentheses possible; it does not need to be unique.
The key observations are that lowercase letters are always valid and do not need removal, and that the problem can be solved in linear time by carefully tracking unmatched parentheses. Important edge cases include strings that are entirely parentheses, strings with all valid parentheses, strings with letters interspersed with unmatched parentheses, and strings that become empty after removal.
Approaches
The brute-force approach would involve generating all possible strings by removing various combinations of parentheses and checking each one for validity. While correct, this is extremely inefficient because the number of combinations grows exponentially with the number of parentheses.
The optimal approach uses a stack to track indices of unmatched opening parentheses '(' and processes the string in two passes. The first pass removes unmatched closing parentheses ')' by skipping them if there is no corresponding opening parenthesis in the stack. The second pass removes any remaining unmatched opening parentheses by using the indices stored in the stack. This ensures the minimum number of removals because we only remove parentheses that are unmatched.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Generate all subsets of parentheses and check validity |
| Optimal | O(n) | O(n) | Use a stack to track unmatched parentheses and build a valid string in linear time |
Algorithm Walkthrough
- Initialize an empty stack to store indices of unmatched
'('characters and an empty set to record indices of parentheses to remove. - Iterate over the string from left to right. For each character, if it is
'(', push its index onto the stack. If it is')'and the stack is not empty, pop the stack (matching a pair). If it is')'and the stack is empty, mark this index for removal. - After completing the first pass, any indices left in the stack correspond to unmatched
'('. Mark these indices for removal as well. - Build the resulting string by iterating over the original string and skipping any character whose index is marked for removal.
- Return the resulting string.
Why it works: By maintaining the stack, we ensure that every ')' has a matching '(' before it, and any remaining '(' without a match is removed. This guarantees that the resulting string is valid and that the minimum number of parentheses is removed because we never remove matched pairs.
Python Solution
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stack = []
to_remove = set()
for i, char in enumerate(s):
if char == '(':
stack.append(i)
elif char == ')':
if stack:
stack.pop()
else:
to_remove.add(i)
to_remove.update(stack)
result = []
for i, char in enumerate(s):
if i not in to_remove:
result.append(char)
return ''.join(result)
The Python implementation uses a stack to track unmatched '(' characters and a set to_remove to store indices of unmatched ')'. The first loop iterates through the string to find unmatched parentheses. After the first loop, any remaining indices in the stack are unmatched '(', which are added to to_remove. Finally, we iterate over the string again to construct the result while skipping indices in to_remove.
Go Solution
func minRemoveToMakeValid(s string) string {
stack := []int{}
toRemove := make(map[int]bool)
for i, char := range s {
if char == '(' {
stack = append(stack, i)
} else if char == ')' {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
} else {
toRemove[i] = true
}
}
}
for _, idx := range stack {
toRemove[idx] = true
}
var result []rune
for i, char := range s {
if !toRemove[i] {
result = append(result, char)
}
}
return string(result)
}
In Go, we use a slice as a stack and a map toRemove to store indices of unmatched parentheses. The approach is identical to the Python version, but Go requires explicit conversion from string to rune slice when appending characters to handle Unicode safely, even though the problem constraints are ASCII letters and parentheses.
Worked Examples
Example 1: "lee(t(c)o)de)"
| Index | Char | Stack | To Remove |
|---|---|---|---|
| 0 | l | [] | {} |
| 1 | e | [] | {} |
| 2 | e | [] | {} |
| 3 | ( | [3] | {} |
| 4 | t | [3] | {} |
| 5 | ( | [3,5] | {} |
| 6 | c | [3,5] | {} |
| 7 | ) | [3] | {} |
| 8 | o | [3] | {} |
| 9 | ) | [] | {} |
| 10 | d | [] | {} |
| 11 | e | [] | {} |
| 12 | ) | [] | {12} |
Result after removing index 12: "lee(t(c)o)de"
Example 2: "a)b(c)d"
| Index | Char | Stack | To Remove |
|---|---|---|---|
| 0 | a | [] | {} |
| 1 | ) | [] | {1} |
| 2 | b | [] | {1} |
| 3 | ( | [3] | {1} |
| 4 | c | [3] | {1} |
| 5 | ) | [] | {1} |
| 6 | d | [] | {1} |
Result: "ab(c)d"
Example 3: "))(("
| Index | Char | Stack | To Remove |
|---|---|---|---|
| 0 | ) | [] | {0} |
| 1 | ) | [] | {0,1} |
| 2 | ( | [2] | {0,1} |
| 3 | ( | [2,3] | {0,1} |
Result: ""
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | We iterate over the string twice, first to track unmatched parentheses and second to build the result. |
| Space | O(n) | The stack and the set of indices can each grow up to n in the worst case. |
The algorithm is linear in both time and space because each character is processed a constant number of times, and the data structures scale linearly with the input size.
Test Cases
# Provided examples
assert Solution().minRemoveToMakeValid("lee(t(c)o)de)") == "lee(t(c)o)de" # unmatched ')' at the end
assert Solution().minRemoveToMakeValid("a)b(c)d") == "ab(c)d" # unmatched ')' in the middle
assert Solution().minRemoveToMakeValid("))((") == "" # all parentheses unmatched
# Edge cases
assert Solution().minRemoveToMakeValid("") == "" # empty string
assert Solution().minRemoveToMakeValid("abc") == "abc" # no parentheses
assert Solution().minRemoveToMakeValid("(((abc") == "abc" # unmatched '(' at the start
assert Solution().minRemoveToMakeValid("abc)))") == "abc" # unmatched ')' at the end
assert Solution().minRemoveToMakeValid("(a(b(c)d)e)f)") == "(a(b(c)d)e)f" # nested valid parentheses
assert Solution().minRemoveToMakeValid("((a)((b))") == "((a)((b)))"[0:len("((a)((b))")] # unmatched '(' in nested structure
| Test | Why |
|---|---|
"lee(t(c)o)de)" |
Handles unmatched closing parenthesis at the end |
"a)b(c)d" |
Handles unmatched closing parenthesis in the middle |
"))((" |
All parentheses unmatched, result is empty |
"" |
Empty string input |
"abc" |
No parentheses, should remain unchanged |
"(((abc" |
Unmatched opening parentheses at the start |
"abc)))" |
Unmatched closing parentheses at the end |
"(a(b(c)d)e)f)" |
Nested valid parentheses, only extra ')' removed |
Edge Cases
One important edge case is a string that contains only parentheses, such as "))((". In this case, all parentheses are unmatched, and the correct result is an empty string. A naive implementation that assumes letters exist might fail here.
A second edge case is a string where all parentheses are properly nested but some letters are present in between, such as "(a(b)c)". The algorithm correctly preserves letters and matches parentheses because it only removes unmatched parentheses.
A third edge