678. Valid Parenthesis String

class Solution:
    def checkValidString(self, s: str) -> bool:
        """ main idea: check open parathesis --  to make valid parathesis, we need to make sure in the end there are 0 open parethesis 
        
        but in the mean time of looping through s, we need to make sure current substring has open parethesis in order to go on 
        Also with consideration of *, we not sure exact amount of open parenthesis, so we can get a estimate range 
        => create cmax, cmin to keep tracking max, min number of open parethesis  => numbre of close parenthesis we are expecting next  
        => cmin is number of close parenthesis this substring MUST meet  => cmin >=0
           cmax is number of close parenthesis this substring at most CAN be 
           => s is valid if the other substring has ')'  within [cmin,cmax]
                if cmax < 0: there is not way s will be valid 
                     Note, here cmin can't be negtive 
                     if cmin = max(cmin,0)
        """
        cmin=cmax= 0 
        for c in s:
            if c == '(':
                cmin += 1
                cmax += 1
            elif c == ')':
                cmin -= 1
                cmax -= 1
            else:# * 
                cmin -= 1 
                cmax += 1
            if cmax < 0:
                return False 
            cmin = max(cmin,0)
        return cmin == 0