A string s contains only { and }. In one move you may flip a single character (turn { into } or vice versa). Return the minimum number of flips needed to make s balanced, or -1 if it is impossible.
Examples
Input: s = "}{"
Output: 2
Input: s = "{{}}}}"
Output: 1
Explanation: flip the fifth character: "{{}}{}".
Input: s = "{{{"
Output: -1
Explanation: an odd-length string can never be balanced.
Input: s = "}}{{"
Output: 2
Constraints
0 <= len(s) <= 10**5- Target:
O(n)time
Goals
- Cancel out already-matched pairs before reasoning
- Reason about how flips fix a run of unmatched closers followed by openers