Validate Parentheses String with Wildcards

Treat each * as potentially (, ), or empty, but do not enumerate three choices per position. Scan left to right maintaining low and high, the minimum and maximum possible unmatched opening parentheses after the prefix. For ( increment both; for ) decrement both; for * decrement low and increment high. If high becomes negative, even the most optimistic interpretation cannot match a closing parenthesis, so reject. Clamp low to zero because it represents a count, and extra wildcard closings can be treated as empty instead. At the end, accept exactly when low is zero, meaning some interpretation closes every open parenthesis. The key invariant is that all feasible open counts between low and high are reachable, so the range loses no relevant information. Test empty input, only wildcards, a leading ), and a suffix of unmatched opens. Time is O(n), space O(1).