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:
 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.
 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:
(*))
^
 /\
_/\ \____
\
\
 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: ')'.
 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:
(*)(
^

 /\/
_/\_/