☕ DSA Java Articles

Topics › Strings › Hard String Problems

Minimum number of bracket reversals to make an expression balanced

Hard TUF ID 983 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a string s that contains only the characters { and }. In one operation you may reverse a single bracket, turning a { into } or a } into {. Return the minimum number of reversals that make the expression balanced, or -1 if no number of reversals can balance it.

An expression is balanced when every opening bracket is closed later and pairs nest properly: {}, {{}} and {}{} are balanced, while }{ and {{} are not. A handy equivalent: scan left to right with a counter that goes up on { and down on }. The string is balanced exactly when the counter never drops below zero and finishes at zero.

Constraints: 0 ≤ n ≤ 10^5. The empty string is balanced and needs 0 reversals.

Example 1

s = "}{{}}{{{"
answer = 3        // reverse positions 0, 5 and 7: "{{{}}}{}"

Example 2

s = "{{}{{{}{{}}{{"
answer = -1       // 13 characters: an odd count can never pair up

Example 3

s = "}{"
answer = 2        // both brackets face the wrong way: "{}"

Two facts that drive every approach

Odd length is hopeless. Reversals never change the length, and a balanced string has exactly as many { as }, so its length is even. If n is odd, return -1 immediately. If n is even, an answer always exists: for example, rewriting the string as {}{}...{} uses at most n reversals.

Matched pairs can be ignored. Any { that is already closed by a later } can be cancelled together with it, exactly as a stack checker for parentheses does. What remains after all cancellations cannot contain {} anywhere, so it must look like }}}...{{{: some c unmatched closing brackets followed by some o unmatched opening brackets. Because n is even and every cancellation removes two characters, c + o is even, so c and o are both even or both odd.

For the leftover }}}...{{{ the cheapest repair is clear. Reverse every other } so that }} becomes {}, and reverse every other { so that {{ becomes {}. If c and o are both odd, one }{ remains in the middle and both of its brackets need reversing. That gives

answer = ceil(c / 2) + ceil(o / 2) = (c + 1) / 2 + (o + 1) / 2   (integer division)

The approaches below differ only in how they find c and o, plus one exhaustive method that confirms the formula.

Approach 1: Brute force

Intuition. Each bracket is either reversed or left alone, so there are 2^n possible sets of reversals. Try every set, check whether the resulting string is balanced with the counter test, and keep the smallest set that works. It is far too slow for real inputs, but it makes no assumptions at all, which is exactly what we want from a reference to test the clever methods against.

Algorithm.

  1. If n is odd, return -1.
  2. For every bit mask from 0 to 2^n - 1, reverse the characters whose bits are set.
  3. Run the counter check. If the string is balanced and the mask has fewer set bits than the best so far, record it.
  4. Return the best count.
static int bruteForce(String s) {
    int n = s.length();
    if (n % 2 == 1) return -1;
    if (n > 20) throw new IllegalArgumentException("brute force is for tiny inputs only");
    int best = Integer.MAX_VALUE;
    for (int mask = 0; mask < (1 << n); mask++) {
        int flips = Integer.bitCount(mask);
        if (flips >= best) continue;
        int balance = 0;
        boolean ok = true;
        for (int i = 0; i < n && ok; i++) {
            char c = s.charAt(i);
            if ((mask >> i & 1) == 1) c = (c == '{') ? '}' : '{';
            balance += (c == '{') ? 1 : -1;
            if (balance < 0) ok = false;
        }
        if (ok && balance == 0) best = flips;
    }
    return best;
}

Complexity. Time O(2^n · n): every mask is checked in linear time. Space O(1) beyond the input. The method refuses inputs longer than 20 characters; the Java file uses it to verify the other two methods on every bracket string of length up to 10.

Approach 2: Better, cancel pairs with a stack

Intuition. Implement the second fact literally. Push each character; when a } arrives and the top of the stack is a {, they form a matched pair, so pop instead of pushing. Whatever is left on the stack is the }}}...{{{ leftover, and counting its two kinds gives c and o.

Algorithm.

  1. If n is odd, return -1.
  2. For each character: if it is } and the stack top is {, pop; otherwise push it.
  3. Count the { and } left on the stack.
  4. Return (open + 1) / 2 + (close + 1) / 2.
static int withStack(String s) {
    if (s.length() % 2 == 1) return -1;
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '}' && !st.isEmpty() && st.peek() == '{') st.pop();   // cancel a matched pair
        else st.push(c);
    }
    int open = 0, close = 0;                 // the leftover looks like }}}...{{{
    for (char c : st) {
        if (c == '{') open++;
        else close++;
    }
    return (open + 1) / 2 + (close + 1) / 2;
}

Complexity. Time O(n): each character is pushed and popped at most once. Space O(n) for the stack in the worst case, for example a string of only {.

Approach 3: Optimal, two counters

Intuition. The stack only ever holds } characters below { characters, and we never look deeper than the top. So it is enough to know how many unmatched { are waiting (open) and how many } could not be matched (close). A } either closes a waiting { (decrement open) or, if none is waiting, becomes permanently unmatched (increment close), because no later { can ever close a bracket that came before it.

Algorithm.

  1. If n is odd, return -1.
  2. Set open = 0 and close = 0.
  3. For each character: on { do open++; on } do open-- if open > 0, otherwise close++.
  4. Return (open + 1) / 2 + (close + 1) / 2.
static int optimal(String s) {
    if (s.length() % 2 == 1) return -1;
    int open = 0, close = 0;                 // unmatched '{' and unmatched '}' seen so far
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '{') open++;
        else if (open > 0) open--;           // this '}' closes an earlier '{'
        else close++;                        // nothing to close: an unmatched '}'
    }
    return (open + 1) / 2 + (close + 1) / 2;
}

Dry run on s = "}{{}}{{{":

i char open close note
0 } 0 1 nothing to close
1 { 1 1  
2 { 2 1  
3 } 1 1 closes position 2
4 } 0 1 closes position 1
5 { 1 1  
6 { 2 1  
7 { 3 1  

The answer is (3 + 1) / 2 + (1 + 1) / 2 = 2 + 1 = 3, matching Example 1.

Complexity. Time O(n), one pass. Space O(1), two integers.

Why the formula cannot be beaten

Achieving ceil(c / 2) + ceil(o / 2) was shown above. Here is why no solution can use fewer reversals, even one that also touches already-matched brackets.

Track the running balance (+1 for {, -1 for }). With the counter method, the balance equals open - close, and it reaches a new minimum exactly when close increases, so its lowest value is -c. Let P be the first position where the balance is -c.

The two groups are disjoint, so every valid solution uses at least ceil(c / 2) + ceil(o / 2) reversals.

Edge cases and pitfalls