Minimum number of bracket reversals needed to make an expression balanced

Problem Statement

Given an expression string containing only { and }, find the minimum number of bracket reversals needed to make the expression balanced.

Example:

• Input: "}{"

• Output: 2

• Explanation: Reverse both brackets to get {}

• Input: "{{{{"

• Output: 2

• Explanation: Reverse last two {{ to }} to get {{}}

• Input: "{{{{}}"

• Output: 1

• Explanation: One expression is already balanced, need to reverse one { to }

• Input: "}{{}}{{{"

• Output: 3

Note: If string length is odd, it's impossible to balance.

Approach 1: Using Stack

Intuition

First, remove all balanced pairs using a stack. The remaining string will have the form }}}...{{{. We need to reverse these remaining brackets.

Algorithm

1. Use stack to remove balanced pairs
2. After processing, stack contains unbalanced brackets
3. Count remaining { and } brackets
4. Calculate reversals needed

import java.util.*;

public class Solution {
    public int minReversals(String expr) {
        int n = expr.length();
        
        // Odd length can never be balanced
        if (n % 2 != 0) {
            return -1;
        }
        
        Stack<Character> stack = new Stack<>();
        
        // Remove balanced pairs
        for (char c : expr.toCharArray()) {
            if (c == '{') {
                stack.push(c);
            } else {
                if (!stack.isEmpty() && stack.peek() == '{') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        
        // Count unbalanced brackets
        int openCount = 0;
        int closeCount = 0;
        
        while (!stack.isEmpty()) {
            if (stack.pop() == '{') {
                openCount++;
            } else {
                closeCount++;
            }
        }
        
        return (closeCount + 1) / 2 + (openCount + 1) / 2;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through the string
• Space Complexity: O(n) - Stack can hold all characters in worst case

Approach 2: Optimal (Using Counter)

Intuition

We don't need a stack. Just count unmatched brackets using two counters.

Algorithm

1. Track count of unmatched opening brackets
2. When we see }, either match with existing { or count as unmatched
3. Calculate reversals from unmatched counts

public class Solution {
    public int minReversals(String expr) {
        int n = expr.length();
        
        if (n % 2 != 0) {
            return -1;
        }
        
        int openCount = 0;
        int closeCount = 0;
        
        for (char c : expr.toCharArray()) {
            if (c == '{') {
                openCount++;
            } else {
                if (openCount > 0) {
                    openCount--;
                } else {
                    closeCount++;
                }
            }
        }
        
        return (openCount + 1) / 2 + (closeCount + 1) / 2;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(1) - Only using counters

Understanding the Formula

After removing balanced pairs, we have:

• closeCount unmatched }
• openCount unmatched {

The pattern looks like: }}}...{{{

Why ceil(count/2)?

1. For }}}} (4 closing):

   • Reverse 2 to get {{}} ✓
   • Reversals = ceil(4/2) = 2

2. For }}} (3 closing):

   • This is odd, but combined with opening it works
   • If we have }}}{{{ → reverse middle ones → {}{}{}
   • Reversals needed for }}} part = ceil(3/2) = 2

3. For {{{{ (4 opening):

   • Reverse 2 to get {{}} ✓
   • Reversals = ceil(4/2) = 2

4. For }}{{{:

   • closeCount = 2, openCount = 3
   • Reversals = ceil(2/2) + ceil(3/2) = 1 + 2 = 3
   • }}{{{ → {}{{{ → {}{{}} or variations

Edge Cases

Extended: Multiple Types of Brackets

For expressions with (), {}, []:

Key Takeaways

1. Remove balanced pairs first to simplify the problem
2. After removal, the pattern is }}}...{{{
3. Formula: ceil(close/2) + ceil(open/2)
4. Odd length strings can never be balanced
5. Space can be optimized from O(n) to O(1) using counters
6. This is a classic greedy problem
7. The intuition: pair up unmatched brackets and reverse one in each pair

Related Problems

1. Minimum Add to Make Parentheses Valid (LeetCode 921)
2. Minimum Remove to Make Valid Parentheses (LeetCode 1249)
3. Valid Parentheses (LeetCode 20)
4. Longest Valid Parentheses (LeetCode 32)