NeetCode #151LC-1249MediumArrays & Hashing
← Back to All Problems#151 · #1249 · Minimum Remove to Make Valid Parentheses(移除无效的括号)
📌 Problem Statement & Constraints
Given a string
s of '(', ')' and lowercase letters, remove the minimum number of parentheses so that the resulting string is valid. Return any valid result. Constraints: 1 <= s.length <= 10^5.💡 Core Algorithmic Approaches
- Scan left to right with a stack of indices of unmatched
'('. - On
'(', push its index. On')', pop if the stack is non-empty; otherwise the')'is unmatched, so mark its index for removal. - After the scan, any indices left on the stack are unmatched
'('and must also be removed. - Build the result by skipping the marked indices. This is the standard minimum-removal greedy.
💻 Benchmark Python3 Implementation
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stack = [] # indices of unmatched '('
remove = set() # indices to delete
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
elif ch == ")":
if stack:
stack.pop() # matched with the most recent '('
else:
remove.add(i) # unmatched ')'
remove.update(stack) # unmatched '(' left over
return "".join(ch for i, ch in enumerate(s) if i not in remove)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass to mark and one pass to build the result.
💾 Space Complexity
O(n) for the stack and the removal set.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the leftover
'('on the stack: they are unmatched and must be removed too. - Removing letters as well as parentheses: only parentheses may be removed; letters are always kept.
- Trying to keep the string balanced with the minimum removals by counting alone: you need the positions, not just the counts, to rebuild the string.
- Using a single counter instead of a stack: it works for this problem (the minimum removal count is determined by counting), but you still need positions to construct the output.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.