1249.Minimum Remove to Make Valid Parentheses

• Link: 1249. Minimum Remove to Make Valid Parentheses - Medium
• Track: NeetCode150

Question

Restate the problem

• Given a string s with letters and parentheses, remove the minimum number of parentheses to make it valid (every ( has a matching ) and vice versa).
• Return any valid result.

Edge Case

• No parentheses → return as-is
• All parentheses, no letters → may return ""
• Nested: "(((" → remove all

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Stack + Set	$O(n)$	$O(n)$
Method 2	Two-pass balance	$O(n)$	$O(n)$

Method 1 - Stack + Set

Key

The stack only ever holds ( indices, so it naturally catches both problems:

• stack is empty when ) arrives → unmatched );
• indices still in stack after full scan → unmatched (.

Approach

• Use a stack to track indices of unmatched (. Use a set to track indices to remove.
  1. Scan left to right
     • ( → push its index onto stack
     • ) → if stack has a match, pop it (valid pair found); else mark this ) index for removal
  2. After the scan, any indices still in the stack are unmatched ( → add them to remove set
  3. Rebuild the string, skipping indices in the remove set

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Code

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = [] # only store left parentheses
        remove = set()
 
        for i, char in enumerate(s):
            if char == "(":
                stack.append(i)
            
            if char == ")":
                if stack:
                    stack.pop()
                else:
                    remove.add(i)
            
        remove.update(stack)
        
        res = []
        for i, char in enumerate(s):
            if i not in remove:
               res.append(char)
 
        return "".join(res)

Method 2 - Two-pass balance

Approach

• Two-pass without a stack. Use a balance counter instead of tracking indices.

  • Pass 1 (left → right): remove invalid ) — any ) when balance == 0 has no matching (, skip it.
  • Pass 2 (right → left): remove invalid ( — any ( when right_balance == 0 has no matching ), skip it.

• Key insight: after pass 1, all ) are valid. But some ( may still be unmatched — pass 2 cleans those up by scanning backwards.

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Code

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        res = []
        balance = 0
 
        # first pass: remove invalid ')'
        for c in s:
            if c not in "()":
                res.append(c)
            elif c == "(":
                balance += 1
                res.append(c)
            else:  # c == ")"
                if balance > 0:
                    balance -= 1
                    res.append(c)
 
        ans = []
        right_balance = 0
 
        # second pass: remove invalid '('
        for i in range(len(res) - 1, -1, -1):
            c = res[i]
            if c not in "()":
                ans.append(c)
            elif c == ")":
                right_balance += 1
                ans.append(c)
            else:  # c == "("
                if right_balance > 0:
                    right_balance -= 1
                    ans.append(c)
 
        ans.reverse()
        return "".join(ans)

---

Mistake