Leetcode 1249. Minimum Remove to Make Valid Parentheses

This problem asks us to clean up a string with potentially mismatched square brackets by removing the minimum number of brackets to make it valid. A valid string means every '(' has a corresponding ')' that comes after it, and every ')' has a corresponding '(' that comes before it.

The key insight is that we want to preserve as many matched bracket pairs as possible while removing the unmatched ones. This is essentially a bracket matching problem with the added complexity of needing to identify which specific brackets to remove.

We need to handle two types of invalid brackets: closing brackets that don't have matching opening brackets before them, and opening brackets that don't have matching closing brackets after them.

The most straightforward approach would be to generate all possible combinations of removing parentheses and check which ones result in valid strings.

We could use bit manipulation or recursion to generate every possible subset of characters to remove. For a string of length n with k parentheses, we'd generate 2^k different combinations, removing different sets of parentheses each time.

For each combination, we'd need to validate if the resulting string has balanced parentheses by counting open and close brackets. This means for each of the 2^k combinations, we perform an O(n) validation check.

While this guarantees finding a solution with minimum removals, it's extremely inefficient for larger inputs and doesn't leverage the inherent structure of the parentheses matching problem.

def minRemoveToMakeValid(s):
    n = len(s)
    best_result = ""
    max_valid_length = 0
    for mask in range(1 << n):
      cand = ''.join(s[i] for i in range(n) if mask & (1 << i))
      if isValidParentheses(cand) and len(cand) > max_valid_length:
        max_valid_length = len(cand)
        best_result = cand
    return best_result
def isValidParentheses(s):
    open_count = 0
    for ch in s:
      if ch == '(': open_count += 1
      elif ch == ')':
        if open_count == 0: return False
        open_count -= 1
    return open_count == 0

The breakthrough insight is that we can solve this in two phases: first identify unmatched closing brackets (those that come without preceding opening brackets), then identify unmatched opening brackets (those left without following closing brackets). The stack handles both phases elegantly by tracking the matching process.

After seeing the brute force limitations, a stack is the perfect data structure because it naturally models the Last-In-First-Out behavior of bracket matching. When we encounter an opening bracket, we're waiting for its corresponding closing bracket - this is exactly what a stack represents.

The stack's LIFO property ensures that when we find a closing bracket, it matches with the most recent unmatched opening bracket, which is exactly how proper bracket nesting works. This allows us to identify matched pairs in real-time as we scan through the string.

Moreover, the stack automatically keeps track of unmatched opening brackets - anything left on the stack after processing represents brackets that need to be removed.

Now that we understand why a stack is perfect for tracking parentheses state, here's how we implement it efficiently:

We make two passes through the string. In the first pass, we use a stack (or counter) to identify unmatched closing parentheses - these must be removed since they have no corresponding opening parenthesis before them.

During this pass, we push opening parentheses onto our stack and pop when we encounter closing parentheses. Any closing parenthesis that finds an empty stack is marked for removal.

In the second pass (going right-to-left), we handle excess opening parentheses. After the first pass, we know how many valid pairs we can form. Any opening parentheses beyond this count must be removed.

This two-pass approach ensures we remove the minimum number of parentheses while maintaining the relative order of all remaining characters.

def minRemoveToMakeValid(s):
    # First pass: remove invalid closing parentheses
    stack = []
    result = []
    for char in s:
        if char == '(': 
            stack.append('(')
            result.append(char)
        elif char == ')':
            if stack:
                stack.pop()
                result.append(char)
            # else: skip invalid closing
        else:
            result.append(char)
    # Second pass: right-to-left remove excess opening parentheses
    open_needed = 0
    out = []
    for char in reversed(result):
        if char == ')':
            open_needed += 1
            out.append(char)
        elif char == '(':
            if open_needed > 0:
                open_needed -= 1
                out.append(char)
            # else: drop extra '('
        else:
            out.append(char)
    return ''.join(reversed(out))

• Stack for nested structure validation: Use a stack whenever you need to match opening and closing elements in nested structures - the stack's LIFO nature perfectly mirrors how nested parentheses must be closed in reverse order of opening.
• Two-pass strategy for constraint optimization: When dealing with both excess opening and closing elements, use two passes - first pass removes invalid closing brackets greedily, second pass removes leftover opening brackets, ensuring minimum total removals.
• Index-based stack tracking: Store indices of opening parentheses in the stack rather than the characters themselves - this enables efficient marking of unmatched elements for removal while preserving string structure during reconstruction.
• Greedy validation with immediate filtering: Remove invalid closing parentheses immediately when no matching opening parenthesis exists (empty stack), but defer removal of excess opening parentheses until after the full scan to avoid premature decisions.
• Set conversion for O(1) lookup optimization: Convert remaining stack indices to a set before the second pass - this transforms the removal check from O(n) list search to O(1) set lookup, crucial for large inputs with many unmatched parentheses.
• Incremental string building pattern: Build the result string character by character rather than modifying the original string - this avoids expensive string operations and makes the algorithm more readable and debuggable for parentheses validation problems.