678. Valid Parenthesis String

• if left max < 0, it is not valid even with wildcards
• if left min < 0, we can choses to use wildcard, set min = 0

The reason that we reset the leftMin to zero is, if the decrement of leftMin is caused by ')', if the string is invalid, the error would be captured by leftMax < 0 condition already. Hence this can only be due to star

class Solution(object):
    def checkValidString(self, s):
        leftMin, leftMax = 0, 0

        for c in s:
            if c == '(':
                leftMin, leftMax = leftMin + 1, leftMax + 1
            elif c == ')':
                leftMin, leftMax = leftMin - 1, leftMax - 1
            else:
                leftMin, leftMax = leftMin - 1, leftMax + 1

            if leftMax < 0:
                return False
            if leftMin < 0:
                leftMin = 0

        return leftMin == 0