678. Valid Parenthesis String

Given a string of '(', ')' and '*', return true if it can be valid, where each '*' may be treated as '(', ')' or an empty string.

Track the smallest and largest possible number of unmatched '(' so far. '(' raises both, ')' lowers both, '*' widens the range by one each way. Fail if max < 0; clamp min at 0; succeed if min ends at 0.

1function checkValidString(s: string): boolean {
2  let lo = 0, hi = 0;
3  for (const c of s) {
4    if (c === "(") { lo++; hi++; }
5    else if (c === ")") { lo--; hi--; }
6    else { lo--; hi++; }
7    if (hi < 0) return false;
8    lo = Math.max(lo, 0);
9  }
10  return lo === 0;
11}

lo = 0hi = 0

s

(

)

No open parentheses yet: range [0, 0].

1 / 0

Space: play/pause · ←/→: step