921. Minimum Add to Make Parentheses Valid

O(n) time O(1) space
l和r分别表示无法匹配的左括号跟右括号的个数

class Solution {
public:
    int minAddToMakeValid(string S) {
        int l = 0, r = 0;
        for (char c : S) {
            if (c == '(') {
                ++l;
            } else if (c == ')') { // 当前字符是右括号且左括号有余则可以进行匹配，用掉一个左括号，否则增加一个无法匹配的右括号
                l > 0 ? --l : ++r;
            }
        }
        return l + r;
    }
};

class Solution {
public:
    int minAddToMakeValid(string S) {
        int debt = 0, balance = 0;
        for (char c : S) {
            balance += c == '(' ? 1 : -1;
            if (balance < 0) { // 如果balance为负，说明欠钱了，先赊账，让balance平衡，最后debt和balance一起算
                ++debt;
                ++balance;
            }
        }
        return debt + balance;
    }
};

stack O(n) time O(n) space

class Solution {
public:
    int minAddToMakeValid(string S) {
        stack<char> s;
        for (char c : S) {
            if (c == ')' && !s.empty() && s.top() == '(') {
                s.pop();
            } else {
                s.push(c);
            }
        }
        return s.size();
    }
};