# Consise Java solution, O(N) time, O(1) space, with reasoning and drawings

• Here is the final solution:

``````class Solution {
public boolean checkValidString(String s) {
int lo = 0, hi = 0;
for (int i = 0; i < s.length(); i++) {
hi += s.charAt(i) != ')' ? +1 : -1;
lo += s.charAt(i) != '(' ? -1 : +1;
if (hi < 0) { return false; }
lo = Math.max(0, lo);
}
return lo <= 0 && 0 <= hi;
}
}
``````

My reasoning when solving the problem:

1. I recalled a similar simpler problem: if we have only ( and ), we need to track a balance variable (+1 when '(', -1 when ')'), checking two conditions 1) 0 <= balance at each step 2) 0 == balance at the end.
2. I noticed, that '*' in that model 'modifies' the balance by -1, 0, +1. So we may replace a scalar balance with a range and check if there is a value in the range that satisfies to the above two checks. To help reasoning I drew an example:
``````(*))
^
|  /\
|_/\ \____
\
\
``````
1. Noticed a possible problem here: with this approach the same '*' can be interpreted differently ('(', ')', '') during different checks. To be shure I draw an example:
``````*)((
^
|
|    /
|_/\/ ____
\  /
\/
``````

Here for intermediate check '*' would represent '(', and for the final check: ')'.

1. I evaluated couple of ideas and concluded that is should be sufficient to shrink the range when it goes below zero. Here is an example:
``````(*)(
^
|
|  /\/
|_/\_/
``````

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