Minimum Number of Swaps to Make The String Balanced

You are given a string s of even length n, with exactly n / 2 opening brackets [ and n / 2 closing brackets ]. You may swap any two characters. Return the minimum number of swaps to make the brackets balanced. This is LeetCode 1963.

Example 1
Input: s = "][]["
Output: 1
Explanation: swap index 0 with index 3 to get "[[]]".
Example 2
Input: s = "]]][[["
Output: 2
Explanation: swap 0 with 4 to get "[]][][", then 1 with 5 to get "[[][]]".
Example 3
Input: s = "[]"
Output: 0

How to Think About It

Step 1: Cancel what already matches

Scan from left to right. Every ] that has an unmatched [ before it closes that bracket, and the pair can be ignored. What is left over always looks like ]]]...[[[: some unmatched closing brackets, then the same number of unmatched opening ones. Let m be that number.

Step 2: One swap fixes two

Swap the first leftover ] with the last leftover [. "]]][[[" becomes "[]][][": the swapped pair now encloses everything between them, and two leftover pairs are fixed by one swap.

Step 3: The formula

So m leftover pairs need ceil(m / 2) = (m + 1) / 2 swaps. For m = 3 that is 2; for m = 1 it is 1.

Step 4: Counting m

Keep open, the unmatched [ so far. A ] either decreases open, if it is positive, or is an unmatched closing bracket, so it adds one to unmatched.

Walkthrough

s = "]]][[[".

Characteropen afterunmatched after
]01
]02
]03
[ [ [33

m = 3, so (3 + 1) / 2 = 2 swaps.

Java Solution

No swaps are actually made; only the count of leftover brackets is needed.

Java
public class MinimumNumberOfSwapsToMakeTheStringBalanced {

    public static int minSwaps(String s) {
        int open = 0;                         // '[' still waiting for a match
        int unmatched = 0;                    // ']' with no '[' before them
        for (char c : s.toCharArray()) {
            if (c == '[') {
                open++;
            } else if (open > 0) {
                open--;                       // this ']' closes an earlier '['
            } else {
                unmatched++;
            }
        }
        return (unmatched + 1) / 2;           // each swap fixes two unmatched ']'
    }

    public static void main(String[] args) {
        System.out.println(minSwaps("][]["));     // 1
        System.out.println(minSwaps("]]][[["));   // 2
        System.out.println(minSwaps("[]"));       // 0
    }
}

The original implementation, MinSwapsToMakeStringBalanced.java, is on GitHub.

Complexity

  • Time: O(n).
  • Space: O(1).

Matching brackets with a counter, or with a stack when there are several kinds, is the basis of Valid Parentheses.