Minimum Bracket Reversals
01 · Problem
You are given a string s made up only of the characters '{' and '}'. In one move you may pick any single character and reverse it, turning '{' into '}' or vice versa.
Return the minimum number of moves needed to make s balanced. A string is balanced when every '{' can be matched with a later '}' and every '}' closes an earlier '{' (for example "{{}}" and "{}{}" are balanced, "}{" is not). If no sequence of moves can balance the string, return -1.
02 · Examples
s = "}{{}}{{{"3
After cancelling the matched "{{}}", the leftover is "}{{{" with c = 1 unmatched '}' and o = 3 unmatched '{'. The answer is ceil(1/2) + ceil(3/2) = 1 + 2 = 3, for example "}{{{" -> "{{}}" by flipping positions 0, 2 and 3 of the leftover.
s = "{{}{{{}{{}}{{"-1
The string has odd length 13, so it can never be balanced.
s = "}}{{"2
Flip the first '}' to '{' and the last '{' to '}' giving "{}{}": 2 reversals.
03 · Constraints
- 011 <= s.length <= 105
- 02s[i] is either '{' or '}'
- 03The length of s may be odd
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.