Minimum Remove to Make Valid Parentheses

How it works

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.

Steps

1. Count total closing parentheses in the string (closeCnt).
2. Initialize openCnt = 0 and an empty result list.
3. 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.
4. Return the result as a string.

Complexity

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

Things to watch for

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.

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)

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int openCnt = 0, closeCnt = 0;
        for (char& c : s) {
            if (c == ')') closeCnt++;
        }

        string res;
        for (char& c : s) {
            if (c == '(') {
                if (openCnt == closeCnt) continue;
                openCnt++;
            } else if (c == ')') {
                closeCnt--;
                if (openCnt == 0) continue;
                openCnt--;
            }
            res.push_back(c);
        }

        return res;
    }
};