Valid Parenthesis - Greedy Range

Track $lo$ (min possible open count) and $hi$ (max possible open count). For '(': both increase by $1$. For ')': both decrease by $1$. For '*': $lo$ decreases (could be ')'), $hi$ increases (could be '('). Keep $lo \geq 0$ (clamp it).

If $hi < 0$, there are too many ')' no matter what. At end, check $lo = 0$. The range $[lo, hi]$ represents the minimum and maximum possible open parentheses count at each position.

If $hi < 0$, there are too many ')' no matter how you assign '*'.

If $lo = 0$ at the end, some assignment of '*' balances the string. Clamping $lo$ to $0$ handles impossible negative counts.