1249. Minimum Remove to Make Valid Parentheses - Explanation

Description

You are given a string s consisting of lowercase English characters, as well as opening and closing parentheses, ( and ).

Your task is to remove the minimum number of parentheses so that the resulting string is valid.

Return the resulting string after removing the invalid parentheses.

A parentheses string is valid if all of the following conditions are met:

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.

Example 1:

Input: s = "nee(t(c)o)de)"

Output: "nee(t(c)ode)"

Explanation: "nee(t(co)de)" , "nee(t(c)o)de" would also be accepted.

Example 2:

Input: s = "x(y)z("

Output: "x(y)z"

Example 3:

Input: s = "))()(("

Output: "()"

Constraints:

1 <= s.length <= 100,000.
s is made up of lowercase English characters and parentheses ().

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Stack

Intuition

A string of parentheses is valid when every opening parenthesis has a matching closing one, and they nest properly. The key insight is that we can process the string in two passes. In the first pass (left to right), we skip any closing parenthesis that doesn't have a matching open one. After this pass, we know exactly how many unmatched opening parentheses remain. In the second pass (right to left), we remove those excess opening parentheses from the end.

Algorithm

Initialize an empty result list and a counter cnt to track unmatched opening parentheses.
First pass (left to right): For each character:
- If it's (, add it to result and increment cnt.
- If it's ) and cnt > 0, add it and decrement cnt (it matches an open paren).
- If it's ) and cnt == 0, skip it (no matching open paren).
- If it's any other character, add it to result.
Second pass (right to left): Traverse the result and skip the first cnt opening parentheses.
Reverse and return the filtered result as a string.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        res = []
        cnt = 0  # extra ( parentheses
        for c in s:
            if c == "(":
                res.append(c)
                cnt += 1
            elif c == ")" and cnt > 0:
                res.append(c)
                cnt -= 1
            elif c != ")":
                res.append(c)

        filtered = []
        for c in reversed(res):
            if c == "(" and cnt > 0:
                cnt -= 1
            else:
                filtered.append(c)
        return "".join(reversed(filtered))

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Without Stack

Intuition

This approach follows the same logic as the stack solution but modifies the string in place. Instead of building a new result list during the first pass, we mark invalid closing parentheses directly in the original array. The second pass still removes excess opening parentheses from the right side.

Algorithm

Convert the string to a character array and initialize counter cnt for unmatched opening parentheses.
First pass: Iterate through the array:
- If it's (, increment cnt.
- If it's ) and cnt > 0, decrement cnt.
- If it's ) and cnt == 0, mark this position as empty (invalid closing paren).
Second pass (right to left): Skip the first cnt opening parentheses while building the result.
Reverse and return the result string.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        arr = list(s)
        cnt = 0  # extra ( parentheses
        for i, c in enumerate(s):
            if c == "(":
                cnt += 1
            elif c == ")" and cnt > 0:
                cnt -= 1
            elif c == ")":
                arr[i] = ''

        res = []
        for c in reversed(arr):
            if c == '(' and cnt > 0:
                cnt -= 1
            else:
                res.append(c)

        return ''.join(reversed(res))

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Stack (Optimal)

Intuition

Instead of using a counter, we can use a stack to store the indices of unmatched opening parentheses. When we see a closing parenthesis, we either pop from the stack (if there's a matching open) or mark it as invalid. After the first pass, any indices remaining in the stack are unmatched opening parentheses that need removal.

Algorithm

Convert the string to a character array and initialize an empty stack.
Iterate through the array:
- If it's (, push its index onto the stack.
- If it's ) and stack is not empty, pop the stack (found a match).
- If it's ) and stack is empty, mark this index as invalid.
After iteration, mark all indices remaining in the stack as invalid (unmatched opening parens).
Build the result by including only characters at valid positions.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s = list(s)
        stack = []
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c == ')':
                if stack:
                    stack.pop()
                else:
                    s[i] = ''

        while stack:
            s[stack.pop()] = ''
        return ''.join(s)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Without Stack (Optimal)

Intuition

We can solve this in a single pass by counting closing parentheses upfront. Knowing the total number of ) characters tells us the maximum number of ( we can keep. As we iterate, we track how many opening parentheses we've included and use this to decide whether each parenthesis should be kept or skipped.

Algorithm

Count total closing parentheses in the string (closeCnt).
Initialize openCnt = 0 and an empty result list.
Iterate through each character:
- If it's (: Skip it if openCnt == closeCnt (no room for more opens). Otherwise, increment openCnt and add it.
- If it's ): Decrement closeCnt. Skip if openCnt == 0 (no matching open). Otherwise, decrement openCnt and add it.
- For other characters, add directly to result.
Return the result as a string.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        openCnt = closeCnt = 0
        for c in s:
            closeCnt += c == ')'

        res = []
        for c in s:
            if c == '(':
                if openCnt == closeCnt:
                    continue
                openCnt += 1
            elif c == ')':
                closeCnt -= 1
                if openCnt == 0:
                    continue
                openCnt -= 1
            res.append(c)

        return ''.join(res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output string.

Common Pitfalls

Only Handling One Direction

A common mistake is only removing unmatched closing parentheses in a left-to-right pass and forgetting that opening parentheses can also be unmatched. For example, the string "(((a" has three unmatched ( characters that need removal. You must either use a two-pass approach (first remove invalid ), then remove invalid (), or track indices of unmatched parentheses explicitly.

Removing Wrong Opening Parentheses

When there are excess opening parentheses, some solutions incorrectly remove the first occurrences instead of the last ones. Since we process left-to-right to match parentheses, the unmatched ( characters are always the rightmost ones. Removing from the left can break valid pairs that were already matched.

Modifying String While Iterating

Attempting to modify the string in place while iterating over it leads to index shifting bugs. For instance, if you delete a character at index 3, all subsequent indices shift left by one. Use a separate result array or mark invalid positions first, then build the final string in a second pass.