# Python easy understand solution

• The number of open parenthesis is in a range `[cmin, cmax]`
`cmax` counts the maximum open parenthesis, which means the maximum number of unbalanced '(' that COULD be paired.
`cmin` counts the minimum open parenthesis, which means the number of unbalanced '(' that MUST be paired.

The string is valid for 2 condition:

1. `cmax` will never be negative.
2. `cmin` is 0 at the end.
``````def checkValidString(self, s):
cmin = cmax = 0
for i in s:
if i == '(':
cmax += 1
cmin += 1
if i == ')':
cmax -= 1
cmin = max(cmin - 1, 0)
if i == '*':
cmax += 1
cmin = max(cmin - 1, 0)
if cmax < 0:
return False
return cmin == 0
``````

or shorter:

``````def checkValidString(self, s):
cmin = cmax = 0
for i in s:
cmax = cmax-1 if i==')' else cmax+1
cmin = cmin+1 if i=='(' else max(cmin - 1, 0)
if cmax < 0: return False
return cmin == 0
``````

Edited after vonzcy's suggestion.

• @lee215 why cant cmin be less than 0?

• @topcoder4309

`cmin` means the number of unbalanced '(' that MUST be paired and `cmax` means the maximum number of unbalanced '(' that COULD be paired. If you don't have enough MUST, supply with COULD.

• @topcoder4309
cmax considers each '*' as '(', which should never be negative
cmin considers each '*' as ')' as much as possible (treat it as empty string if cmin<0 -- "max(cmin-1, 0)").
In the end, cmin should be 0. If it's larger than 0, it means even if we consider every '*' as ')', there is still some '(' left.

• @lee215 what if s=')(*)',your code will return True, but '(' doesn't go before the ')', it confused me the code could be accept

• @Newfish_01 If s=')(*)', it will return `False` at the first char.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.