Valid Parenthesis - Implementation

Here is the solution:

function checkValidString(s)
 lo := 0
 hi := 0
 for c in s
 if c = '(' then
 lo := lo + 1
 hi := hi + 1
 else if c = ')' then
 lo := lo - 1
 hi := hi - 1
 else
 lo := lo - 1
 hi := hi + 1
 if hi < 0 then
 return false
 lo := max(lo, 0)
 return lo = 0

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

The range $[lo, hi]$ covers all possible open counts. If $0$ is in range at the end, some assignment of '*' makes the string valid.