• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
bool checkValidString(const string& s) {
int low = 0;   // lower bound of valid '(' count
int high = 0;  // upper bound of valid '(' count

for (const char c : s) {
switch (c) {
case '(':
++low;
++high;
break;
case ')':
low = max(0, --low);
--high;
break;
case '*':
low = max(0, --low);
++high;
break;
}
if (high < 0)
return false;
}

return low == 0;
}
};
``````

## JAVA

``````class Solution {
public boolean checkValidString(final String s) {
int low = 0;  // lower bound of valid '(' count
int high = 0; // upper bound of valid '(' count

for (final char c : s.toCharArray()) {
switch (c) {
case '(':
++low;
++high;
break;
case ')':
low = Math.max(0, --low);
--high;
break;
case '*':
low = Math.max(0, --low);
++high;
break;
}
if (high < 0)
return false;
}

return low == 0;
}
}
``````

## Python

``````class Solution:
def checkValidString(self, s: str) -> bool:
low = 0
high = 0

for c in s:
if c == '(':
low += 1
high += 1
elif c == ')':
if low > 0:
low -= 1
high -= 1
else:
if low > 0:
low -= 1
high += 1
if high < 0:
return False

return low == 0
``````