Problem - Valid Parenthesis String

Given a string with '(', ')', and '', determine if it can be valid. The '' can be '(', ')', or empty. For $s = "(*)$", it is valid ('' can be ')'). For $s = "(*))$", also valid ('' is empty). For $s = ")("$, invalid. Track the range of possible open parentheses counts. Tricky: the '*' wildcard introduces ambiguity.

You do not know which role it plays until you finish scanning. The range-based greedy tracks all possible open counts simultaneously, avoiding the need to try all $3^k$ assignments where $k$ is the number of '*'.