lo, hi respectively be the smallest and largest possible number of open left brackets after processing the current character
c in the string. Every integer in this interval is possible to attain.
If we see a
'(', we know that we must have one extra left bracket, otherwise we could have one less. If we don't see a
')', we know we could have one extra left bracket, otherwise we must have one less.
If at any point the maximum number of open left brackets is negative, then it is impossible to make a valid string. At the end, we want to know if it was possible to have exactly 0 open left brackets.
def checkValidString(self, s): lo = hi = 0 for c in s: lo += 1 if c == '(' else -1 hi += 1 if c != ')' else -1 if hi < 0: break lo = max(lo, 0) return lo == 0