[Medium] LC 1249: Minimum Remove to Make Valid Parentheses

Difficulty: Medium
Category: String, Stack
Companies: Amazon, Facebook, Microsoft, Google

Problem Statement

Given a string s of '(', ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, contains only lowercase characters, or
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.

Examples

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is either '(', ')', or lowercase English letter.

Solution Approaches

Key Insight: Use a stack to track unmatched parentheses and remove them from the string.

Algorithm:

  1. Use stack to track indices of unmatched parentheses
  2. For each character, push '(' indices and pop for matching ')'
  3. Remove all indices remaining in stack (unmatched parentheses)
  4. Return the modified string

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

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        remove = set()

        for idx, char in enumerate(s):
            if char == '(':
                stack.append(idx)
            elif char == ')':
                if stack:
                    stack.pop()
                else:
                    remove.add(idx)

        # add unmatched '(' indices
        remove.update(stack)

        result = []
        for i, char in enumerate(s):
            if i not in remove:
                result.append(char)

        return ''.join(result)

Approach 2: Two-Pass String Building

Algorithm:

  1. First pass: Remove unmatched ')' by tracking balance
  2. Second pass: Remove unmatched '(' by tracking balance in reverse
  3. Build result string

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

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        # First pass: remove invalid ')'
        result = []
        balance = 0

        for c in s:
            if c == '(':
                balance += 1
                result.append(c)
            elif c == ')':
                if balance > 0:
                    balance -= 1
                    result.append(c)
            else:
                result.append(c)

        # Second pass: remove extra '('
        final_result = []
        for c in reversed(result):
            if c == '(' and balance > 0:
                balance -= 1
            else:
                final_result.append(c)

        return ''.join(reversed(final_result))

Approach 3: Set-Based Tracking

Algorithm:

  1. Use two passes to identify invalid parentheses
  2. Use a set to track indices to remove
  3. Build result string excluding tracked indices

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

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        to_remove = set()
        stk = []

        # Find unmatched parentheses
        for i in range(len(s)):
            if s[i] == '(':
                stk.append(i)
            elif s[i] == ')':
                if not stk:
                    to_remove.add(i)
                else:
                    stk.pop()

        # Add remaining unmatched '('
        while stk:
            to_remove.add(stk.pop())

        # Build result string
        result = ""
        for i in range(len(s)):
            if i not in to_remove:
                result += s[i]

        return result

Algorithm Analysis

Approach Comparison

Approach Time Space Pros Cons
Stack-Based O(n) O(n) Simple, intuitive String erasure overhead
Two-Pass O(n) O(n) No string modification More complex logic
Set-Based O(n) O(n) Clear separation of concerns Extra space for set

Key Insights

  1. Stack Validation: Use stack to track parentheses matching
  2. Index Tracking: Store indices instead of characters for removal
  3. Two-Pass Strategy: Handle unmatched parentheses in both directions
  4. Minimal Removal: Remove only the minimum required parentheses

Implementation Details

Stack-Based Approach

# Track indices of unmatched parentheses
stk = []

for idx, ch in enumerate(s):
    if ch == '(':
        stk.append(idx)
    elif ch == ')':
        if stk:
            stk.pop()  # matched with '('
        else:
            stk.append(idx)  # unmatched ')'

String Modification

# Remove unmatched parentheses from str
result = list(s)

while stk:
    result[stk.pop()] = ''

result = ''.join(result)

Edge Cases

  1. Empty String: "" → ""
  2. No Parentheses: "abc" → "abc"
  3. All Unmatched: "))((" → ""
  4. Nested Valid: "(a(b)c)" → "(a(b)c)"
  5. Mixed Characters: "a)b(c)d" → "ab(c)d"

Follow-up Questions

  • What if you needed to return all possible valid strings?
  • How would you handle multiple types of brackets?
  • What if you needed to minimize the number of removals?
  • How would you optimize for very large strings?

Optimization Techniques

  1. Stack Index Tracking: Store indices instead of characters
  2. Single Pass: Use stack to identify all unmatched parentheses
  3. String Building: Avoid multiple string modifications
  4. Memory Efficiency: Use minimal extra space

Code Quality Notes

  1. Readability: Stack approach is most intuitive
  2. Performance: All approaches have O(n) time complexity
  3. Space Efficiency: O(n) space for stack/set storage
  4. Robustness: Handles all edge cases correctly

This problem demonstrates the power of stack-based validation for parentheses matching and shows how to efficiently remove invalid characters while preserving valid structure.