Leetcode 1249. Minimum Remove to Make Valid Parentheses

Asked at:

Meta

DESCRIPTION

Given a string containing brackets '(', ')' and lowercase letters, remove the minimum number of brackets to make the string valid. A valid string has properly matched brackets where every opening bracket has a corresponding closing bracket in the correct order.

Input:


s = "(h(e)ll(o)"

Output:


"(h(e)llo)"

Explanation: Remove the '(' before 'o' to balance the brackets.

Constraints:

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

Note: Multiple valid answers may exist - return any valid string

Understanding the Problem

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.

Brute Force Approach

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

Initialize array from input string for brute force enumeration

0 / 3074

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n * 2^k) Due to checking all possible combinations

Space Complexity: O(n) Additional space for tracking

Building Intuition

What Data Structure is Ideal for this Problem?

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.

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.

Common Mistakes

Trying to solve in one pass and missing unmatched opening brackets at the end

Not handling the case where all brackets are unmatched

Forgetting that letters should always be preserved in the output

Attempting to modify the string in-place instead of building a new result

Optimal Solution

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))

result = []

0 / 23

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) Single pass through the data

Space Complexity: O(n) Space for the data structure

What We've Learned

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.

Test Your Understanding

Why is stack the right data structure for this problem?

stack provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early September, 2025

Meta

Mid-level

Early September, 2025

Meta

Senior

Early September, 2025

Meta

Senior

Get Premium to View All 60+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Leetcode 1249. Minimum Remove to Make Valid Parentheses

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

What Data Structure is Ideal for this Problem?

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact