1541. Minimum Insertions to Balance a Parentheses String

O(n) time O(1) space

class Solution {
public:
    int minInsertions(string s) {
        int res = 0, stk = 0;
        for (int n = size(s), i = 0; i < n; ++i) {
            if (s[i] == '(') {
                stk += 2; // 需要两个)
            } else if (i + 1 < n && s.substr(i, 2) == "))") {
                if (stk == 0) {
                    ++res; // 缺一个(
                } else {
                    stk -= 2; // 需要两个)
                }
                ++i; // 连续两个)，多移一位
            } else {
                ++res; // 缺一个)
                if (stk == 0) {
                    ++res; // 缺一个(
                } else {
                    stk -= 2; // 需要两个)
                }
            }
        }
        return res + stk; // 一个(需要两个)，stk的步长为2
    }
};

O(n) time O(n) space

class Solution {
public:
    int minInsertions(string s) {
        string stk;
        int res = 0;
        for (int n = size(s), i = 0; i < n; ++i) {
            if (s[i] == '(') {
                stk += s[i];
            } else if (i + 1 < n && s.substr(i, 2) == "))") {
                if (empty(stk)) {
                    ++res;
                } else {
                    stk.pop_back();
                }
                ++i;
            } else {
                ++res;
                if (empty(stk)) {
                    ++res;
                } else {
                    stk.pop_back();
                }
            }
        }
        return res + size(stk) * 2;
    }
};