# 0678. Valid Parenthesis String
###### tags: `Leetcode` `Medium` `FaceBook` `Parentheses`
Link: https://leetcode.com/problems/valid-parenthesis-string/
## 思路
一开始想要用[0921. Minimum Add to Make Parentheses Valid](https://hackmd.io/BW_TqN0oTsq6f0gxlYxXHw)的方法，分别记录余量和星号数，如果余量小于0，就看星号数能不能把余量补到0，不行就return false，最后看余量是不是大于0，如果余量大于星号数，就return false
但发现不行的原因是那种方法是在最后把所有的)补在最后面，所以产生的string肯定是valid的，但是这题是补在$*$处，所以可能补完的字串不是valid字串

正确思路，用两个变数cmax，cmin 分别记录 the maximum/minimum open parenthesis
## Code

class Solution {
    public boolean checkValidString(String s) {
        int cmax = 0, cmin = 0;
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i)=='('){
                cmax++;
                cmin++;
            }
            else if(s.charAt(i)==')'){
                cmax--;
                cmin--;
            }
            else{
                cmax++; //*->(
                cmin--; //*->)
            }
            if (cmax < 0) return false;
            // Currently, don't have enough open parentheses to match close parentheses-> Invalid, For example: ())(
            cmin = Math.max(cmin, 0);   
            // It's invalid if open parentheses count < 0 that's why cmin can't be negative
        }
        return cmin == 0; // Return true if can found `openCount == 0` in range [cmin, cmax]
    }
    }
}