OA: Fewest deletions to balance parentheses

s contains only ( and ). A string is balanced if every ( can be paired with a later ) and nothing is left unpaired. The empty string is balanced.

Write min_deletions(s: str) -> int, the fewest characters you must delete from s so the rest is balanced.

Aim for O(n) time and O(1) extra space. Strings can be a million characters long, so repeatedly deleting "()" pairs is too slow.

min_deletions("())(")    # 2
min_deletions("(()")     # 1
min_deletions("()()")    # 0