Minimum Number of Swaps to Make the String Balanced

medium two pointers greedy string

Problem

You are given a 0-indexed string s of even length n, made of exactly n/2 opening brackets [ and n/2 closing brackets ]. A string is balanced if it is empty, or two balanced strings concatenated, or a balanced string wrapped in [ ]. You may swap the brackets at any two indices any number of times. Return the minimum number of swaps needed to make s balanced.

Inputs = "]]][[["

Output2

Swap index 0 with 4, then index 1 with 5, giving "[[][]]".

Inputs = "]["

Output1

One swap turns "][" into "[]".

s (only [ and ], even length, balanced counts)

def min_swaps(s):
    arr = list(s)
    swaps = bal = 0
    j = len(arr) - 1
    for i in range(len(arr)):
        if arr[i] == '[':
            bal += 1
        else:
            bal -= 1
        if bal < 0:
            while arr[j] != '[':
                j -= 1
            arr[i], arr[j] = arr[j], arr[i]
            swaps += 1
            bal += 2
            j -= 1
    return swaps

function minSwaps(s) {
  const arr = s.split("");
  let swaps = 0, bal = 0;
  let j = arr.length - 1;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === "[") bal += 1;
    else bal -= 1;
    if (bal < 0) {
      while (arr[j] !== "[") j -= 1;
      [arr[i], arr[j]] = [arr[j], arr[i]];
      swaps += 1;
      bal += 2;
      j -= 1;
    }
  }
  return swaps;
}

int minSwaps(String s) {
    char[] arr = s.toCharArray();
    int swaps = 0, bal = 0;
    int j = arr.length - 1;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == '[') bal += 1;
        else bal -= 1;
        if (bal < 0) {
            while (arr[j] != '[') j -= 1;
            char t = arr[i]; arr[i] = arr[j]; arr[j] = t;
            swaps += 1;
            bal += 2;
            j -= 1;
        }
    }
    return swaps;
}

int minSwaps(string s) {
    int swaps = 0, bal = 0;
    int j = (int)s.size() - 1;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '[') bal += 1;
        else bal -= 1;
        if (bal < 0) {
            while (s[j] != '[') j -= 1;
            swap(s[i], s[j]);
            swaps += 1;
            bal += 2;
            j -= 1;
        }
    }
    return swaps;
}

Explanation

We scan the string left to right with a pointer i while keeping a running balance bal: +1 for every [ and -1 for every ]. As long as bal stays at 0 or above, every closing bracket so far has a matching open before it, so no fix is needed there.

The trouble starts the moment bal goes negative. That means we just read a ] with no open bracket waiting for it. To repair it cheaply we bring in an open bracket from the far end: a second pointer j walks leftward from the back until it finds a [, and we swap that [ into position i.

After the swap the character at i is now [, so the balance jumps by 2 (from -1 back to +1): the misplaced ] is parked at the far end where it harmlessly closes brackets, and we count one swap. Because j only moves left and i only moves right, the two pointers never cross back, giving a single linear pass.

Each swap fixes the deepest deficit greedily, and it can be shown no balanced arrangement needs fewer swaps. The number of swaps equals the ceiling of (maximum unmatched closing depth) divided by 2, which the converging pointers compute implicitly.

Example: "]]][[[". The first ] drives bal to -1, so j grabs the last [ and swaps — one swap. A later ] dips negative again and triggers a second swap. Total: 2.

Time: O(n) Space: O(n)