280. Valid Parenthesis String

Track the range [lo, hi] of how many '(' could still be open. A '*' widens the range (it might be '(', ')' or empty); if hi ever goes negative there are too many ')', and if lo can reach 0 by the end the string is valid.

Two counters bound the possibilities

• hi = maximum possible open parentheses (treat every * as ().
• lo = minimum possible open parentheses (treat every * as )), floored at 0.

For each character:

• ( → lo++, hi++.
• ) → lo--, hi--.
• * → lo--, hi++ (it could go either way).

If hi < 0 at any point, even the most generous reading has unmatched ) → return false. Clamp lo at 0 (you can't have negative open parens). At the end, the string is valid iff lo == 0 (some assignment closes everything).

Worked example

"(*)": ( → lo1,hi1; * → lo0,hi2; ) → lo0(clamped),hi1. End lo==0 → true.

Complexity

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

class Solution {
    public boolean checkValidString(String s) {
        int lo = 0, hi = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                lo++;
                hi++;
            } else if (c == ')') {
                lo--;
                hi--;
            } else {  // '*'
                lo--;
                hi++;
            }
            if (hi < 0) return false;
            if (lo < 0) lo = 0;
        }
        return lo == 0;
    }
}