Valid Parenthesis String

A string s is made of the characters (, ) and *. Each * is a wildcard that you may replace with (, with ), or with nothing at all, independently of the other stars.

Write can_balance(s: str) -> bool that returns True if some choice for the stars makes s a balanced bracket string: every ( is closed by a later ), and no ) appears without an open ( before it. The empty string counts as balanced.

can_balance("(*)")    # True    star = nothing
can_balance("(*))")   # True    star = "("
can_balance("((*")    # False   one star can close only one of the two
can_balance(")*(")    # False   the first ")" has nothing to close
can_balance("*")      # True
can_balance("")       # True

Constraints:

• 0 <= len(s) <= 2 * 10^5
• s contains only (, ) and *

Trying all 3^stars choices is hopeless, and remembering every possible count of open brackets is still O(n²). Aim for O(n) time and O(1) extra space.