Minimum number of bracket reversals to make an expression balanced
HardCancel matched pairs, then pair up the rest
Problem
Given a string of '{' and '}', return the minimum reversals to make it balanced, or -1 if impossible.
Cancel matched pairs; from the leftover opens and closes, each pair needs about half a reversal.
The idea
Remove every matched '{}' pair with a stack, leaving a string of the form '}}}{{{'. Each pair of leading '}' costs one reversal and each pair of trailing '{' costs one, with a leftover of one each costing two more.
The trick
- Odd length is impossible — return -1 immediately.
- Answer = ceil(close/2) + ceil(open/2) on what remains after cancelling.
- Counters suffice; the stack is only for intuition.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — }{{}}{{{ Values: 0.
1remove matched pairs (stack)2let open=o, close=c leftover3if (o+c) odd: -14return ceil(o/2)+ceil(c/2)Input
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "}}{{"
- Output:
- 2
- Explanation:
- Flip two brackets to balance → 2.
Example 2
- Input:
- s = "{{{{}}"
- Output:
- 1
- Explanation:
- One reversal fixes it.
Example 3
- Input:
- s = "{{{"
- Output:
- -1
- Explanation:
- Odd length can't balance → -1.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.