Minimum Add to Make Parentheses Valid

Intuitionwhy every insertion corresponds to one unmatched parenthesis

Scan the string from left to right while tracking how many open parentheses are currently available to match a closing parenthesis. An open parenthesis increases that supply. A closing parenthesis consumes one if possible; otherwise it has no earlier partner, so you must insert an open parenthesis before it. That insertion is forced, and it fixes exactly one unmatched close.

After the scan, any open parentheses still in the balance have never found a closing partner. Each one requires one inserted close after it or at a suitable later position. Therefore the answer has two independent parts: insertions forced while scanning for unmatched closes, plus insertions needed for opens left over at the end. No insertion can fix two unmatched parentheses, so this count is minimum.

Approachcount forced insertions without storing the stack

1. 1Set open and close to zero. open counts available unmatched opening parentheses, while close counts insertions already forced by unmatched closing parentheses; separating them keeps the two kinds from being confused.
2. 2For each character, increment open when it is '(', because this creates one new parenthesis that a later ')' may match.
3. 3For a ')', decrement open when open is positive, because an existing unmatched '(' is its valid partner and no insertion is needed.
4. 4For a ')', increment close when open is zero, because no earlier '(' can match it and an inserted '(' is unavoidable.
5. 5After the scan, return open + close, because every remaining unmatched '(' needs one inserted ')', while close already counts the inserted '(' characters required earlier.
6. 6Process the characters once from left to right instead of repeatedly searching for partners, because each parenthesis has one matching decision and no character needs to be revisited.

Complexityconstant working memory

Annotated solutionC++ · one pass · counter-based

#include <string>
using namespace std;

class Solution {
public:
    int minAddToMakeValid(string s) {
        int open = 0, close = 0;

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

        return open + close;
    }
};

The important placement is the open > 0 check before decrementing. A closing parenthesis can match only an opening parenthesis that appeared earlier and remains unused. If none exists, increasing close records the one insertion that must occur; at the end, open records the opposite repair. The algorithm never needs to construct the repaired string because only the number of forced insertions matters.

The stack alternativea direct matching model that costs more space

A stack can model the same process more literally: push every '(', and pop when a ')' has an available match. If the stack is empty for a ')', count an inserted '('. The stack left at the end represents unmatched opens, so its size is added to the count. This is a reasonable version when you want to preserve unmatched characters, but it is not an optimisation: it uses O(n) extra space instead of O(1).

#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    int minAddToMakeValid(string s) {
        stack<char> unmatchedOpen;
        int insertions = 0;

        for (char c : s) {
            if (c == '(') {
                unmatchedOpen.push(c);
            } else if (!unmatchedOpen.empty()) {
                unmatchedOpen.pop();
            } else {
                insertions++;
            }
        }

        return insertions + static_cast<int>(unmatchedOpen.size());
    }
};

Common mistakesthe two counting errors that change the minimum