Minimum number of swaps for bracket balancing

The problem, simply

You get a string with the same number of [ and ]. One swap trades two brackets that stand next to each other. Find the fewest swaps that make the string balanced: reading left to right, you never have more ] than [ so far.

For example []][][ needs 2 swaps to become [][][].

A story to remember it

Picture it

Examples

Way 1: the simple way

Do the swaps for real. Walk the string with a counter of spare tickets. When you meet a ] with no spare ticket, find the next [ to the right and bubble it back, one neighbor swap at a time, until it stands where the ] was.

1. Keep depth: how many [ are still open.
2. On [, add 1. On ] with depth > 0, subtract 1.
3. On ] with depth == 0, find the next [ at j, swap it back to i, and add j - i swaps. Now position i holds a [, so depth becomes 1.

class Solution {
    public int minSwaps(String s) {
        char[] a = s.toCharArray();
        int swaps = 0, depth = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == '[') {
                depth++;
            } else if (depth > 0) {
                depth--;
            } else {
                int j = i + 1;
                while (a[j] != '[') j++;          // the next ticket kid
                while (j > i) {                   // walk it forward, one trade at a time
                    char t = a[j]; a[j] = a[j - 1]; a[j - 1] = t;
                    j--;
                    swaps++;
                }
                depth = 1;                        // a[i] is now '['
            }
        }
        return swaps;
    }
}

How long it takes: each bubble can walk across most of the string, so O(n^2). Extra room: the character array, O(n).

Way 2: the clever way

We never need to move anything. When a [ arrives, the number of swaps it needs is the number of ] that are waiting before it. So keep that number, the imbalance.

1. Count open (how many [ so far) and close (how many ] so far).
2. On ]: close++, and set imbalance = close - open. If it is above 0, that many ] are waiting.
3. On [: open++. If imbalance > 0, add imbalance to the swaps (it walks past all of them), then imbalance-- (one of them got its partner).

class Solution {
    public int minSwaps(String s) {
        int open = 0, close = 0, imbalance = 0, swaps = 0;
        for (char c : s.toCharArray()) {
            if (c == '[') {
                open++;
                if (imbalance > 0) {
                    swaps += imbalance;     // walk past every waiting ]
                    imbalance--;            // one of them gets its partner
                }
            } else {
                close++;
                imbalance = close - open;   // how many ] are waiting now
            }
        }
        return swaps;
    }
}

How long it takes: one walk, O(n). Extra room: four numbers, O(1).

Watch out for

• Take the imbalance before you lower it. The [ walks past all the waiting ], including the one it then pairs with.
• On ], recompute imbalance = close - open instead of adding 1. It may be 0 or below when there were spare [.
• The problem promises equal counts of [ and ]. If not, it can never be balanced, so check counts first if the input is not trusted.

What interviewers ask next

• Any two brackets may be swapped? Count the most lonely ] at any moment (k) and return (k + 1) / 2. One swap fixes two of them.
• Why is this the minimum? Each ] that is waiting must have some [ cross over it, and every neighbor swap moves one [ past one ]. The greedy counts exactly those crossings, no more.
• Flips instead of swaps, with { and }? That is "Minimum number of bracket reversals": ceil(close / 2) + ceil(open / 2).
• Return the final string? It is always the same: follow the counts, or run Way 1 if n is small.

Remember this

Grown-up words: the waiting kids are the imbalance, the trades are adjacent swaps, and moving each [ as early as needed is a greedy choice that counts the inversions between brackets.