678. Valid Parenthesis String

two-pass greedy O(n) time O(1) space
反证即可，如果有反例则一定可以trap，否则就是balanced
There are 3 valid cases:

1. There are more open parenthesis but we have enough ‘*‘ so we can balance the parenthesis with ‘)’
2. There are more close parenthesis but we have enough ‘*‘ so we can balance the parenthesis with ‘(‘
3. There are as many ‘(‘ than ‘)’ so all parenthesis are balanced, we can ignore the extra ‘*‘

Algorithm: You can parse the String twice, once from left to right by replacing all ‘*‘ by ‘(‘ and once from right to left by replacing all ‘*‘ by ‘)’. For each of the 2 loops, if there’s an iteration where you end up with a negative count (SUM[‘(‘] - SUM[‘)’] < 0) then you know the parenthesis were not balanced. You can return false. After these 2 checks (2 loops), you know the string is balanced because you’ve satisfied all the 3 valid cases mentioned above.

class Solution {
public:
    bool checkValidString(string s) {
        int l = 0;
        for (char c : s) {
            l += (c == ')' ? -1 : 1); // 如果所有*都当(
            if (l < 0) return false;
        }
        if (l == 0) return true; // 只是用来加速，可有可无
        int r = 0, n = s.length();
        for (int i = n - 1; i >= 0; --i) {
            r += (s[i] == '(' ? -1 : 1); // 如果所有*都当)
            if (r < 0) return false;
        }
        return true; // 因为既没有左括号过多又没有右括号过多，所以是balanced
    }
};

O(n) 用lo和hi来表示可能的左括号个数减右括号个数之差（只考虑非负数）的区间，
比如(*)，(是[1, 1]，(*是[0, 2]，(*)是[0, 1]

class Solution {
public:
    bool checkValidString(string s) {
        int lo = 0, hi = 0;
        for (char c : s) {
            if (c == '(') { // 遇见左括号，则区间整体加1
                ++lo;
                ++hi;
            } else if (c == ')') { // 遇见右括号，则区间整体减1
                --lo;
                --hi;
            } else { // 遇见*，既可能是左括号，也可能是右括号，则区间扩大lo减1，hi加1
                --lo;
                ++hi;
            }
            if (hi < 0) return false; // 当hi为负时，说明右括号过多，肯定不合法
            lo = max(lo, 0); // lo如果小于0，说明)比(多，是不合法的，如果hi并没有小于0，说明lo小于0是由之前的*造成的，*不一定是)也可能是空字符或者(，所以这里lo时刻要保持为非负数，要排除之前的过多*和)对后边可能产生的影响，比如反例((*)(*))((*如果不维持lo始终非负，则最后会产生false negative，因为前面的*和)让low小于0，后边过多的(虽然让low变成非负，但是结果并不合法
        }
        return lo == 0; // 最后判断一下0是否在区间里
    }
};

class Solution {
public:
    bool checkValidString(string s) {
        int lo = 0, hi = 0;
        for (char c : s) {
            lo += c == '(' ? 1 : -1;
            hi += c == ')' ? -1 : 1;
            if (hi < 0) return false;
            lo = max(lo, 0);
        }
        return lo == 0;
    }
};