Explorer
Data Structures & Algorithms

Find minimum bracket reversals to balance a string of curly braces.

Problem Statement

Given a string `s` consisting of only `{` and `}`, find the minimum number of reversals required to make it balanced. If it is impossible to balance (odd length), return `-1`.

Examples

Input: s = "}{{}}{{"

Output: 2

Explanation: Combining the input according to Minimum number of bracket reversals to make an expression balanced logic yields 2.

Input: s = "{{{"

Output: -1

Explanation: Combining the input according to Minimum number of bracket reversals to make an expression balanced logic yields -1.

Input: s = "}{"

Output: 2

Explanation: Combining the input according to Minimum number of bracket reversals to make an expression balanced logic yields 2.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: If the length of string s is odd, it is impossible to balance. Return -1. šŸ’” Hint 2: Cancel out all already-balanced pairs of brackets {}. šŸ’” Hint 3: The remaining unbalanced brackets will look like }}}...{{{ with count close and open. Minimum reversals needed is ceil(open / 2) + ceil(close / 2).

Editorial & Approach

Problem Overview & Intuition

Any balanced pair {} can be greedily removed. What remains after eliminating balanced pairs will always have the form }}}...{{{ (unmatched closing followed by unmatched opening). Reversing every two adjacent same-direction brackets balances them; if both have an odd residue, two reversals balance the remaining pair.

Step-by-Step Approach

  1. If s.length % 2 !== 0, return -1.
  2. Initialize open = 0 and close = 0.
  3. For each character c in s:
  4. If c === "{", increment open++.
  5. Else if open > 0, decrement open-- (balanced pair).
  6. Else increment close++.
  7. Return Math.ceil(open / 2) + Math.ceil(close / 2).

Optimal Implementation (JavaScript)

function countBracketReversals(s) {
  if (s.length % 2 !== 0) return -1;
  let open = 0, close = 0;
  for (let c of s) {
    if (c === '{') {
      open++;
    } else {
      if (open > 0) open--;
      else close++;
    }
  }
  return Math.ceil(open / 2) + Math.ceil(close / 2);
}

Complexity Analysis

Time Complexity O(N) ā€” single pass through the string.
Space Complexity O(1) ā€” two counter variables.

Edge Cases & Corner Traps Handled

  • Odd length: returns -1 immediately.
  • Already balanced string: returns 0.
  • Completely inverted string "}{": returns 2.

Minimum number of bracket reversals to make an expression balanced

Hard
Given a string `s` consisting of only `{` and `}`, find the minimum number of reversals required to make it balanced. If it is impossible to balance (odd length), return `-1`.
Example Scenarios
1Example 1
Input: s = "}{{}}{{"
Output: 2
Explanation:

Combining the input according to Minimum number of bracket reversals to make an expression balanced logic yields 2.

2Example 2
Input: s = "{{{"
Output: -1
Explanation:

Combining the input according to Minimum number of bracket reversals to make an expression balanced logic yields -1.

3Example 3
Input: s = "}{"
Output: 2
Explanation:

Combining the input according to Minimum number of bracket reversals to make an expression balanced logic yields 2.

Editor
Loading Editor...
s =
"}{{}}{{"
Output:Click "Run" above to execute and verify your code here.
-1