A string s contains (, ) and *. Each * may be treated as a (, a ), or an empty string. Return True if some choice for the wildcards makes the string balanced (every ( closed by a later ), properly nested), otherwise False.
Examples
Input: s = "(*))"
Output: True
Explanation: treat * as "(" to get "(())".
Input: s = "(*)))"
Output: False
Explanation: at most two openers are available for three closers.
Input: s = ")("
Output: False
Constraints
0 <= len(s) <= 10**5- Target:
O(n)time
Goals
- Track the range of possible open-bracket counts instead of one exact count
- Decide whether a wildcard should behave as an opener, a closer, or nothing