Minimum Remove to Make Valid Parentheses — Stack Solution

Given a string with parentheses and lowercase letters, remove the minimum number of parentheses to make the string valid. A valid string has every opening parenthesis matched with a closing one in the correct order.

This is LeetCode 1249, a common Facebook/Meta interview question.

Understanding the Problem

Input:  "lee(t(c)o)de)"
Output: "lee(t(c)o)de"     — removed the last )

Input:  "a)b(c)d"
Output: "ab(c)d"            — removed the first )

Input:  "))(("
Output: ""                  — all invalid, remove everything

The key insight: we need to identify which specific parentheses are unmatched, not just count them.

Approach 1: Stack + Set (Two Pass)

Use a stack to find indices of unmatched parentheses, then build the result string skipping those indices.

def min_remove_to_make_valid(s: str) -> str:
    """
    Remove minimum parentheses to make string valid.
    Time: O(n), Space: O(n)
    """
    stack = []          # stores indices of unmatched '('
    indices_to_remove = set()

    # Pass 1: Find unmatched parentheses
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()  # matched with an opening
            else:
                indices_to_remove.add(i)  # unmatched ')'

    # Any remaining in stack are unmatched '('
    indices_to_remove.update(stack)

    # Pass 2: Build result without invalid indices
    return ''.join(
        char for i, char in enumerate(s)
        if i not in indices_to_remove
    )

Step-by-Step Trace

Input: "lee(t(c)o)de)"

Index: 0  1  2  3  4  5  6  7  8  9  10 11 12
Char:  l  e  e  (  t  (  c  )  o  )  d  e  )

i=0  'l': skip (letter)
i=1  'e': skip
i=2  'e': skip
i=3  '(': push 3         stack=[3]
i=4  't': skip
i=5  '(': push 5         stack=[3,5]
i=6  'c': skip
i=7  ')': pop 5          stack=[3]        ← matches (5
i=8  'o': skip
i=9  ')': pop 3          stack=[]         ← matches (3
i=10 'd': skip
i=11 'e': skip
i=12 ')': stack empty!   remove={12}      ← unmatched

Stack leftover: []
Remove set: {12}

Result: "lee(t(c)o)de" ✓

Approach 2: Two-Pointer Without Stack

Scan left-to-right removing extra ), then right-to-left removing extra (.

def min_remove_two_pass(s: str) -> str:
    """
    Two-pass approach without explicit stack.
    Time: O(n), Space: O(n)
    """
    # Pass 1: Remove unmatched ')' (left to right)
    result = []
    open_count = 0
    for char in s:
        if char == '(':
            open_count += 1
            result.append(char)
        elif char == ')':
            if open_count > 0:
                open_count -= 1
                result.append(char)
            # else: skip unmatched ')'
        else:
            result.append(char)

    # Pass 2: Remove unmatched '(' from right
    final = []
    close_needed = 0
    for char in reversed(result):
        if char == ')':
            close_needed += 1
            final.append(char)
        elif char == '(':
            if close_needed > 0:
                close_needed -= 1
                final.append(char)
            # else: skip unmatched '('
        else:
            final.append(char)

    return ''.join(reversed(final))

Why Two Passes?

Pass	Direction	Removes
1	Left → Right	Unmatched ) (no prior ( to match)
2	Right → Left	Unmatched ( (no later ) to match)

Approach 3: One-Pass with Balance Counter

def min_remove_one_pass(s: str) -> str:
    """
    One-pass using stack for indices.
    Time: O(n), Space: O(n)
    """
    s = list(s)
    stack = []

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                s[i] = ''  # mark for removal

    # Mark remaining unmatched '('
    for i in stack:
        s[i] = ''

    return ''.join(s)

This modifies the list in place, avoiding a second pass through the string.

Edge Cases

# All letters, no parentheses
assert min_remove_to_make_valid("abc") == "abc"

# All invalid
assert min_remove_to_make_valid(")(") == ""

# Already valid
assert min_remove_to_make_valid("(a)(b)") == "(a)(b)"

# Nested valid
assert min_remove_to_make_valid("((()))") == "((()))"

# Multiple removals needed
assert min_remove_to_make_valid("(a(b(c)d") == "a(b(c)d"  # or "(ab(c)d)"

# Empty string
assert min_remove_to_make_valid("") == ""

Complexity Analysis

Approach	Time	Space	Notes
Stack + Set	O(n)	O(n)	Clearest logic
Two-Pass	O(n)	O(n)	No set needed
One-Pass (in-place)	O(n)	O(n)	Fewest iterations

All approaches are O(n) time and space. The stack + set approach is the easiest to explain in interviews.

When to Use This Pattern

• Parentheses validation with modification: When you need to fix (not just check) validity
• Minimum edits: Problems asking for minimum removals/additions
• Index tracking: When you need to know which characters to remove, not just a count

Common Mistakes

1. Counting instead of tracking: Just counting unmatched parens does not tell you which ones to remove
2. Greedy left-to-right only: Removing ) greedily misses unmatched ( that appear earlier
3. Not handling letters: Letters pass through unchanged — only parentheses need logic

Related Problems

• Valid Parentheses — simpler validation check
• Redundant Parentheses — detect unnecessary parens
• Basic Calculator — expression evaluation with parens