Description

Submission

class Solution {
public:
    int minInsertions(string s) {
        int n = s.length();
        int count = 0;      // number of unmatched parentheses so far;
        int ret = 0;

        for(int i = 0; i < n; ++i) {
            char ch = s[i];

            if(ch == '(') ++count;
            else if(ch == ')') {
                if(i+1 < n && s[i+1] == ')') {
                    --count;
                    ++i;
                } else {
                    ++ret;
                    --count;
                }
                if(count < 0) {
                    ++ret;
                    count = 0;
                }
            }
        }

        ret += count * 2;
        return ret;
    }
};