Problem Description

You are given a string s that contains opening parentheses '(', closing parentheses ')', and lowercase English letters.

Your task is to remove the minimum number of parentheses (either '(' or ')') from any positions in the string to make the remaining parentheses valid. Return any valid string after the removal.

A valid parentheses string follows these rules:

• It can be an empty string or contain only lowercase letters
• It can be formed by concatenating two valid strings A and B (written as AB)
• It can be written as (A) where A is a valid string (meaning every opening parenthesis has a matching closing parenthesis in the correct order)

For example:

• "lee(t(c)o)de" is valid (all parentheses are balanced)
• "a)b(c)d" is invalid (the first ) has no matching ()
• "))(( is invalid (parentheses are not in the correct order)

The solution uses a two-pass approach:

1. First pass (left to right): Remove excess closing parentheses ) that don't have matching opening parentheses before them
2. Second pass (right to left): Remove excess opening parentheses ( that don't have matching closing parentheses after them

The algorithm maintains a counter x to track the balance of parentheses. In the first pass, it skips any ) when there are no unmatched ( available. In the second pass, it processes the result from the first pass in reverse, skipping any ( when there are no unmatched ) available. This ensures the minimum number of parentheses are removed while maintaining validity.

Intuition

The key insight is that valid parentheses must satisfy two conditions: every '(' must have a matching ')' that comes after it, and every ')' must have a matching '(' that comes before it.

When we scan from left to right, we can easily identify invalid ')' characters - these are closing parentheses that appear when we haven't seen enough opening parentheses yet. We can keep a counter that increments for '(' and decrements for ')'. If we encounter a ')' when the counter is 0, we know this ')' is invalid and must be removed.

However, this single pass doesn't solve the problem completely. We might have excess '(' characters that never get matched. For example, in "(((", all opening parentheses pass the left-to-right scan, but they're still invalid because they lack matching closing parentheses.

To handle excess '(' characters, we need a second pass from right to left. This time, we treat the problem in reverse - we're looking for '(' characters that don't have matching ')' characters to their right. By processing the string backwards, we can identify and remove these unmatched opening parentheses using the same counter logic.

The brilliance of this two-pass approach is that:

1. The first pass guarantees no ')' appears without a preceding '('
2. The second pass guarantees no '(' remains without a following ')'
3. Together, they ensure we remove the minimum number of parentheses because we only remove characters that definitely cannot be matched

This greedy approach works because once we remove invalid ')' in the first pass, those removals don't affect the validity of the remaining '(' characters - we're simply ensuring balance from both directions.

Learn more about Stack patterns.

Solution Approach

The solution implements a two-pass algorithm to remove invalid parentheses while preserving all valid ones and lowercase letters.

First Pass (Left to Right):

We initialize an empty stack stk and a counter x = 0 to track unmatched opening parentheses. As we iterate through each character c in the string:

• If c is ')' and x == 0, we skip this character (don't add it to the stack) because there's no unmatched '(' to pair with
• If c is '(', we increment x and add it to the stack
• If c is ')' and x > 0, we decrement x and add it to the stack
• If c is a lowercase letter, we simply add it to the stack

After this pass, stk contains all characters except the invalid ')' that appeared without matching '('.

Second Pass (Right to Left):

We reset x = 0 and create a new list ans. We process the stack from the first pass in reverse order (stk[::-1]):

• If c is '(' and x == 0, we skip this character because there's no unmatched ')' to its right
• If c is ')', we increment x and add it to ans
• If c is '(' and x > 0, we decrement x and add it to ans
• If c is a lowercase letter, we add it to ans

Final Result:

Since we processed the characters in reverse during the second pass, we need to reverse ans again to get the correct order: ''.join(ans[::-1]).

The algorithm ensures correctness because:

• The first pass removes all ')' that cannot be matched with a preceding '('
• The second pass removes all '(' that cannot be matched with a following ')'
• Both passes preserve all lowercase letters
• The counter mechanism ensures we only remove the minimum necessary parentheses

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the string, as we make exactly two passes through the string
• Space Complexity: O(n) for storing the intermediate stack and final result

Example Walkthrough

Let's walk through the solution with the example s = "a)b(c)d".

First Pass (Left to Right):

• Start with stk = [] and x = 0 (tracks unmatched ()
• Process each character:
  • 'a': lowercase letter → add to stk → stk = ['a']
  • ')': closing parenthesis with x = 0 (no unmatched () → skip it
  • 'b': lowercase letter → add to stk → stk = ['a', 'b']
  • '(': opening parenthesis → increment x = 1, add to stk → stk = ['a', 'b', '(']
  • 'c': lowercase letter → add to stk → stk = ['a', 'b', '(', 'c']
  • ')': closing parenthesis with x = 1 → decrement x = 0, add to stk → stk = ['a', 'b', '(', 'c', ')']
  • 'd': lowercase letter → add to stk → stk = ['a', 'b', '(', 'c', ')', 'd']

After first pass: stk = ['a', 'b', '(', 'c', ')', 'd'] (removed the invalid first ')')

Second Pass (Right to Left):

• Start with ans = [] and x = 0 (tracks unmatched ))
• Process reversed stk: ['d', ')', 'c', '(', 'b', 'a']
  • 'd': lowercase letter → add to ans → ans = ['d']
  • ')': closing parenthesis → increment x = 1, add to ans → ans = ['d', ')']
  • 'c': lowercase letter → add to ans → ans = ['d', ')', 'c']
  • '(': opening parenthesis with x = 1 → decrement x = 0, add to ans → ans = ['d', ')', 'c', '(']
  • 'b': lowercase letter → add to ans → ans = ['d', ')', 'c', '(', 'b']
  • 'a': lowercase letter → add to ans → ans = ['d', ')', 'c', '(', 'b', 'a']

Final Result: Reverse ans to get the correct order: ''.join(['a', 'b', '(', 'c', ')', 'd']) = "ab(c)d"

The algorithm successfully removed the minimum number of parentheses (just one ')') to make the string valid.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input string s.

The algorithm consists of two main passes through the string:

• First pass: Iterates through each character in s once, performing constant-time operations (checking character type, incrementing/decrementing counter, appending to list). This takes O(n) time.
• Second pass: Iterates through the reversed stk list, which has at most n elements. Each operation within this loop (checking character type, incrementing/decrementing counter, appending to list) takes constant time. This also takes O(n) time.
• Final operation: ''.join(ans[::-1]) requires reversing the ans list (O(n)) and joining the characters (O(n)).

Total time complexity: O(n) + O(n) + O(n) = O(n)

Space Complexity: O(n) where n is the length of the input string s.

The algorithm uses the following additional space:

• stk list: In the worst case (when no characters are removed in the first pass), this stores all n characters from the input string, requiring O(n) space.
• ans list: In the worst case, this stores all valid characters from stk, which could be up to n characters, requiring O(n) space.
• x counter variable: Uses constant space O(1).

Total space complexity: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Remove Parentheses in a Single Pass

A common mistake is trying to identify and remove invalid parentheses in just one pass through the string. This approach fails because you cannot determine if an opening parenthesis '(' is valid until you've seen the entire string after it.

Why it fails:

# Incorrect single-pass attempt
def minRemoveToMakeValid_wrong(s: str) -> str:
    result = []
    balance = 0
    for char in s:
        if char == '(':
            balance += 1
            result.append(char)
        elif char == ')':
            if balance > 0:
                balance -= 1
                result.append(char)
        else:
            result.append(char)
    return ''.join(result)

# This fails for input like "(((" or "a(b(c)d"
# It would return "(((" or "a(b(c)d" instead of "" or "ab(c)d"

Solution: Use the two-pass approach where the first pass handles excess ')' and the second pass (in reverse) handles excess '('.

2. Forgetting to Reverse After the Second Pass

Since the second pass processes characters in reverse order, the result must be reversed again to restore the original order. Forgetting this final reversal is a frequent error.

Why it fails:

# Missing final reversal
def minRemoveToMakeValid_wrong(s: str) -> str:
    # First pass code...
  
    # Second pass
    result = []
    close_count = 0
    for char in reversed(stack):
        # Process characters...
        result.append(char)
  
    return ''.join(result)  # Wrong! This gives reversed output
    # For "lee(t(c)o)de" you'd get "ed)o)c(t(eel"

Solution: Always reverse the result after the second pass: return ''.join(reversed(result))

3. Incorrectly Managing the Counter in the Second Pass

In the second pass, you're processing from right to left, so the logic is inverted - you're counting closing parentheses ')' and matching them with opening parentheses '('.

Why it fails:

# Wrong counter logic in second pass
for char in reversed(stack):
    if char == '(' and open_count == 0:  # Wrong! Should check close_count
        continue
    if char == '(':
        open_count += 1  # Wrong! Should decrement close_count
    elif char == ')':
        open_count -= 1  # Wrong! Should increment close_count

Solution: In the second pass, track close_count: increment for ')' and decrement for '(' when valid.

4. Not Handling Edge Cases Properly

Failing to consider edge cases can lead to unexpected behavior:

• Empty string ""
• String with only letters "abc"
• String with only parentheses "((("
• Completely invalid parentheses ")))((("

Solution: The two-pass approach naturally handles all these cases without special treatment, but it's important to verify your implementation works for them.