Problem
You are given a string s consisting only of characters '(' and ')'.
Repeatedly remove any matched pair of parentheses as part of a valid parentheses matching (equivalently, cancel out all valid matches). After all possible matches are removed, return the number of remaining characters (the count of unmatched parentheses).
Examples
-
s = "()"
→ all matched → return
0
-
s = "())"
→ one pair matched, one
')'
unmatched → return
1
-
s = "(()"
→ one pair matched, one
'('
unmatched → return
1
-
s = ")()("
→ two matched in the middle, ends unmatched → return
2
Function signature
-
Input:
s: string
-
Output:
int
Constraints
-
0 <= len(s) <= 10^6
(design for linear time)
Notes
-
You only need to return the number of unmatched parentheses, not the corrected string.