Minimum number of bracket reversals needed to make an expression balanced

The problem, simply

You get a string made only of { and }. One move flips a single bracket: { becomes } or } becomes {. Find the fewest moves that make the string balanced, which means every { is closed by a } that comes after it, like {{}}{}.

If it can never be balanced, give back -1. That happens when the length is odd, because brackets come in pairs.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every set of flips. With n brackets there are 2^n ways to choose which ones to flip. For each, flip them, check if the result is balanced, and keep the smallest number of flips that works.

1. If n is odd, return -1.
2. For each mask from 0 to 2^n - 1, flip the brackets whose bit is 1.
3. Check balance with a counter: add 1 for {, subtract 1 for }, and it must never drop below 0 and must end at 0.

class Solution {
    public int minReversals(String s) {
        int n = s.length();
        if (n % 2 == 1) return -1;
        int best = Integer.MAX_VALUE;
        for (int mask = 0; mask < (1 << n); mask++) {
            int depth = 0;
            boolean ok = true;
            for (int i = 0; i < n && ok; i++) {
                char c = s.charAt(i);
                if ((mask >> i & 1) == 1) c = (c == '{') ? '}' : '{';   // flip it
                depth += (c == '{') ? 1 : -1;
                if (depth < 0) ok = false;          // a } with no partner
            }
            if (ok && depth == 0) best = Math.min(best, Integer.bitCount(mask));
        }
        return best;
    }
}

How long it takes: 2^n masks, each checked in n steps, so O(2^n * n). Only fine for tiny strings. Extra room: O(n) if you copy the string, O(1) as written.

Way 2: the clever way

Let the matching pairs leave first, using a pile (a stack). Walk the string. A { goes on the pile. A } takes the { on top of the pile as its partner, and both leave. If there is no { to take, the } is lonely and stays at the bottom of the pile.

The leftover pile always looks the same: some lonely } at the bottom and some waiting { on top. So you do not even need to store the pile. Two numbers describe it: close, the lonely }, and open, the waiting {.

1. If the length is odd, return -1.
2. For {, do open++. For }, if open > 0 do open-- (a pair leaves), else close++.
3. Two lonely } need one flip. Two waiting { need one flip. If one of each is left over, that } { needs two flips. All of this is ceil(close / 2) + ceil(open / 2).

class Solution {
    public int minReversals(String s) {
        if (s.length() % 2 == 1) return -1;      // brackets come in pairs
        int open = 0;    // waiting {, the top of the pile
        int close = 0;   // lonely }, the bottom of the pile
        for (char c : s.toCharArray()) {
            if (c == '{') {
                open++;
            } else if (open > 0) {
                open--;                           // a pair holds hands and leaves
            } else {
                close++;                          // no partner for this }
            }
        }
        return (close + 1) / 2 + (open + 1) / 2;  // round each half up
    }
}

How long it takes: one walk over the string, O(n). Extra room: two counters, O(1). If you want to draw it with a real stack, that version uses O(n) room and gives the same answer.

Watch out for

• Check the odd length first. With odd length, open + close is odd and the formula would give a wrong number instead of -1.
• Match a } only with a { that came before it. A { later in the string cannot help it.
• When open and close are left, they are always both even or both odd, because the total length is even. That is why rounding up both halves works.
• Write (x + 1) / 2 for "half, rounded up" with whole numbers. x / 2 rounds down.

What interviewers ask next

• Only ( and ) and you may add brackets instead of flipping? Add open + close brackets: one partner for every leftover.
• Several kinds, like ()[]{}, and you only need to check if it is valid? Push openers on a real stack and check that each closer matches the top.
• Return the fixed string, not just the count? Flip the 1st, 3rd, 5th and so on of the lonely }, and the 1st, 3rd, 5th and so on of the waiting { counted from the end. When both counts are odd, this also flips the } { pair in the middle.
• Allowed to swap any two brackets instead of flipping? That is a different count: see "Minimum number of swaps for bracket balancing".

Remember this

Grown-up words: the pile is a stack, cancelling pairs is stack matching, the lonely and waiting brackets are unmatched closing and opening brackets, and "half rounded up" is the ceiling of x / 2.