Minimum Add to Make Parentheses Valid

Practice Link

Using Stack#

Use a stack to track unmatched opening parentheses. When a ')' is seen and the stack is empty, it has no matching '(', so it must be added — increment the unmatched counter. When a ')' is seen and the stack is non-empty, pop the matched '('. After scanning the full string, every '(' remaining in the stack is also unmatched. The answer is the count of unmatched ')' plus the remaining stack size, giving the minimum number of insertions needed to balance the string.

class Solution {
public:
    int minAddToMakeValid(string s) {
        stack<char> stk;

        int cnt=0;
        for(char c: s)
        {
            if(c=='(')
                stk.push(c);
            else if(c==')' && stk.empty())
                cnt++;
            else
                stk.pop();

        }
        return stk.size() + cnt;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)