Minimum Remove to Make Valid Parentheses

Intuitionvalidity is a prefix condition plus a matching condition

Read the string from left to right and track the number of unmatched opening parentheses. A closing parenthesis is usable only when that count is positive. If the count is zero, no earlier opening parenthesis is available to match it, so keeping this closing parenthesis would make the current prefix invalid. Removing it is forced; no later character can repair a prefix that already has too many closings.

After that scan, every prefix has at least as many opening parentheses as closing parentheses, but the whole string may still contain unmatched openings at the end. Those openings cannot be paired with a later closing parenthesis because there is no later character left. Scan from right to left and remove an opening parenthesis whenever no unmatched closing parenthesis is available for it. Letters never affect either balance and are always preserved.

The two scans remove only forced characters. A closing parenthesis removed on the first pass cannot participate in a valid result, and an opening parenthesis removed on the second pass has no possible partner. Every parenthesis kept by the scans is paired with a parenthesis on the correct side, so the result is valid and the number of removals is minimum.

Approach

1. 1Create a temporary string ans and an open counter, because the first pass needs to preserve the original order while deciding which closing parentheses have a usable opening partner.
2. 2Scan s from left to right. Copy every letter and every opening parenthesis into ans, increasing open for each opening, because neither character can make the current prefix invalid.
3. 3For a closing parenthesis, append it only when open is positive; then decrement open. Otherwise skip it, because a closing parenthesis with open equal to zero would be unmatched in every result that preserves this prefix.
4. 4Create result and scan ans from right to left with a close counter, because the remaining invalid characters can only be unmatched openings and they are easiest to detect from the opposite direction.
5. 5Copy every letter and every closing parenthesis into result, increasing close for each closing, because these characters do not create an unmatched opening while scanning backward.
6. 6For an opening parenthesis, append it only when close is positive; then decrement close. Otherwise skip it, because no closing parenthesis to its right remains available to match it.
7. 7Reverse result before returning it, because the second pass collected kept characters from right to left even though their required output order is left to right.

Complexitythe two scans are linear even when every character is a parenthesis

Annotated solutionC++ · two directional scans · forced removals only

#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string ans;
        int open = 0;

        for (char c : s) {
            if (c == '(') {
                open++;
                ans.push_back(c);
            } else if (c == ')') {
                if (open > 0) {
                    open--;
                    ans.push_back(c);
                }
            } else {
                ans.push_back(c);
            }
        }

        string result;
        int close = 0;

        for (int i = static_cast<int>(ans.size()) - 1; i >= 0; i--) {
            char c = ans[i];
            if (c == ')') {
                close++;
                result.push_back(c);
            } else if (c == '(') {
                if (close > 0) {
                    close--;
                    result.push_back(c);
                }
            } else {
                result.push_back(c);
            }
        }

        reverse(result.begin(), result.end());
        return result;
    }
};

The important placement is the test before appending a closing parenthesis. When open is zero, that closing parenthesis is not merely inconvenient; it is impossible to match without changing the order or inserting a character, neither of which the problem allows. The backward pass uses the symmetric rule for opening parentheses, and the final reverse restores the original left-to-right order.

The index-stack alternativea direct matching arrangement that spends O(n) working memory

A natural alternative is to record the indices of unmatched opening parentheses in a stack and mark every unmatched closing parenthesis for deletion. When a closing parenthesis arrives, match it with the most recent opening index if one exists; otherwise mark the closing index. At the end, mark every opening index still in the stack, then build the answer from unmarked characters.

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        vector<int> openIndices;
        vector<bool> removed(s.size(), false);

        for (int i = 0; i < static_cast<int>(s.size()); i++) {
            if (s[i] == '(') {
                openIndices.push_back(i);
            } else if (s[i] == ')') {
                if (!openIndices.empty()) {
                    openIndices.pop_back();
                } else {
                    removed[i] = true;
                }
            }
        }

        for (int index : openIndices) {
            removed[index] = true;
        }

        string result;
        for (int i = 0; i < static_cast<int>(s.size()); i++) {
            if (!removed[i]) {
                result.push_back(s[i]);
            }
        }
        return result;
    }
};

This is a different arrangement rather than an optimisation. It still takes O(n) time, but the stack of opening indices and the removal marks use O(n) extra space. It can be easier to extend when you need the positions of removed characters, while the two-pass counter solution is shorter and uses only counts to make its decisions.

Common mistakesthe two balance directions must not be mixed