1249. Minimum Remove to Make Valid Parentheses (Medium)

Problem

Given a string s of '(', ')', and lowercase letters, remove the minimum number of parentheses to make the string valid. A valid parenthesis string has every '(' matched by a corresponding ')' in correct order.

Return any valid result (not necessarily unique).

Examples

• "lee(t(c)o)de)" → "lee(t(c)o)de" (remove last ')')
• "a)b(c)d" → "ab(c)d" (remove first ')')
• "))((" → "" (remove all four)
• "(a(b(c)d)" → "a(b(c)d)" or "(a(bc)d)" (either is valid)

LeetCode 1249 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Two-pass stack of indices

Pass 1: Scan left to right. Use a stack to track the indices of unmatched '('. When a ')' is seen:

• If the stack is non-empty, pop the top (the '(' is matched).
• Otherwise, mark this ')' index for removal (it has no opening partner).

After pass 1, all indices remaining in the stack are unmatched '(' that also need removal.

Pass 2: Build the result, skipping any index that was marked.

Python

def min_remove_to_make_valid(s: str) -> str:
    stack = []          # L1: indices of unmatched '('
    remove = set()      # L2: indices to remove

    for i, ch in enumerate(s):              # L3: n iterations (pass 1)
        if ch == "(":
            stack.append(i)                 # L4: O(1) push index of '('
        elif ch == ")":
            if stack:
                stack.pop()                 # L5: O(1) matched pair
            else:
                remove.add(i)              # L6: O(1) unmatched ')'

    remove.update(stack)                   # L7: O(k) remaining '(' are unmatched

    result = []
    for i, ch in enumerate(s):             # L8: n iterations (pass 2)
        if i not in remove:                # L9: O(1) set lookup
            result.append(ch)              # L10: O(1) keep character
    return "".join(result)                 # L11: O(n) join

TypeScript

function minRemoveToMakeValid(s: string): string {
    const stack: number[] = [];             // L1: indices of unmatched '('
    const remove = new Set<number>();       // L2: indices to remove

    for (let i = 0; i < s.length; i++) {   // L3: n iterations (pass 1)
        if (s[i] === '(') {
            stack.push(i);                  // L4: O(1) push index of '('
        } else if (s[i] === ')') {
            if (stack.length) {
                stack.pop();                // L5: O(1) matched pair
            } else {
                remove.add(i);              // L6: O(1) unmatched ')'
            }
        }
    }

    for (const i of stack) remove.add(i);  // L7: remaining '(' are unmatched

    const result: string[] = [];
    for (let i = 0; i < s.length; i++) {   // L8: n iterations (pass 2)
        if (!remove.has(i)) result.push(s[i]);  // L9-L10: O(1) set lookup + keep
    }
    return result.join('');                 // L11: O(n) join
}

Go

func minRemoveToMakeValid(s string) string {
    stack := []int{}           // L1: indices of unmatched '('
    remove := map[int]bool{}   // L2: indices to remove

    for i, ch := range s {     // L3: n iterations (pass 1)
        if ch == '(' {
            stack = append(stack, i)      // L4: O(1) push index of '('
        } else if ch == ')' {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]  // L5: O(1) matched pair
            } else {
                remove[i] = true          // L6: O(1) unmatched ')'
            }
        }
    }
    for _, i := range stack { remove[i] = true } // L7: remaining '(' unmatched

    result := []byte{}
    for i := 0; i < len(s); i++ {       // L8: n iterations (pass 2)
        if !remove[i] { result = append(result, s[i]) } // L9-L10: O(1) keep
    }
    return string(result)                // L11: O(n) convert
}

Swift

final class Solution {
    func minRemoveToMakeValid(_ s: String) -> String {
        let characters = Array(s)
        var openings: [Int] = []
        var remove: Set<Int> = []
        for index in characters.indices {
            if characters[index] == "(" {
                openings.append(index)
            } else if characters[index] == ")" {
                if openings.isEmpty { remove.insert(index) } else { openings.removeLast() }
            }
        }
        remove.formUnion(openings)
        return String(characters.enumerated().compactMap { remove.contains($0.offset) ? nil : $0.element })
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L3-L6 (pass 1, stack ops)	$O(1)$ amortized	n	$O(n)$
L7 (update remove set)	$O(k)$ where k = remaining stack	1	$O(n)$ worst
L8-L10 (pass 2, rebuild)	$O(1)$	n	$O(n)$ ← dominates
L11 (join)	$O(n)$	1	$O(n)$

Complexity

• Time: $O(n)$, two linear passes.
• Space: $O(n)$ for the stack, remove set, and result buffer.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Pass 1 illustrated

s = "lee(t(c)o)de)"
     0123456789...

i=3  '(': push 3.   stack=[3]
i=5  '(': push 5.   stack=[3,5]
i=7  ')': stack non-empty, pop 5 (matched).  stack=[3]
i=9  ')': stack non-empty, pop 3 (matched).  stack=[]
i=13 ')': stack empty, remove.add(13).       stack=[]

After pass 1: stack=[], remove={13}
Pass 2: skip index 13.
Result: "lee(t(c)o)de"

s = "))(("
i=0 ')': stack empty, remove.add(0).  stack=[]
i=1 ')': stack empty, remove.add(1).  stack=[]
i=2 '(': push 2.   stack=[2]
i=3 '(': push 3.   stack=[2,3]

After pass 1: stack=[2,3], remove={0,1}
remove.update([2,3]) -> remove={0,1,2,3}
Pass 2: all skipped.
Result: ""

Why store indices instead of characters

The unmatched ')' are identified immediately (no stack to pop). But unmatched '(' are only known to be unmatched after the full scan: maybe a matching ')' appears later. Storing the index lets us come back and mark them after the scan completes. Storing characters would lose position information.

Key takeaways

• Stack of indices (not characters) is the right representation whenever you need to mark positions for removal after a full scan.
• Unmatched ')' (no opener on the stack) are caught in pass 1 immediately. Unmatched '(' (stack still non-empty after pass 1) are caught by draining the stack into the remove set.
• Using a set for remove gives $O(1)$ lookup in pass 2.
• Any valid answer is accepted, so the two-pass approach (remove minimum, keep order) always produces one correct answer.

Related topics

• Valid Parentheses, stack for matched-pair validation
• Remove All Adjacent Duplicates, stack for character cancellation
• Stacks, underlying data structure

Related concepts

• Stack Parsing, the last open, first closed model for nested syntax and reversible operations.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.