⚡Flashcard Drill➔
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

  1. Scan left to right with a stack of indices of unmatched '('.
  2. On '(', push its index. On ')', pop if the stack is non-empty; otherwise the ')' is unmatched, so mark its index for removal.
  3. After the scan, any indices left on the stack are unmatched '(' and must also be removed.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems