# 1963. Minimum Number of Swaps to Make the String Balanced

## Description

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

• It is the empty string, or
• It can be written as AB, where both A and B are balanced strings, or
• It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

Example 1:

Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".


Example 2:

Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".


Example 3:

Input: s = "[]"
Output: 0
Explanation: The string is already balanced.


Constraints:

• n == s.length
• 2 <= n <= 106
• n is even.
• s[i] is either '[' or ']'.
• The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.

## Solutions

Solution 1: Greedy

We use a variable $x$ to record the current number of unmatched left brackets. We traverse the string $s$, for each character $c$:

• If $c$ is a left bracket, then we increment $x$ by one;
• If $c$ is a right bracket, then we need to check whether $x$ is greater than zero. If it is, we match the current right bracket with the nearest unmatched left bracket on the left, i.e., decrement $x$ by one.

After the traversal, we will definitely get a string of the form "]]]...[[[...". We then greedily swap the brackets at both ends each time, which can eliminate $2$ unmatched left brackets at a time. Therefore, the total number of swaps needed is $\left\lfloor \frac{x + 1}{2} \right\rfloor$.

The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.

• class Solution {
public int minSwaps(String s) {
int x = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == '[') {
++x;
} else if (x > 0) {
--x;
}
}
return (x + 1) / 2;
}
}

• class Solution {
public:
int minSwaps(string s) {
int x = 0;
for (char& c : s) {
if (c == '[') {
++x;
} else if (x) {
--x;
}
}
return (x + 1) / 2;
}
};

• class Solution:
def minSwaps(self, s: str) -> int:
x = 0
for c in s:
if c == "[":
x += 1
elif x:
x -= 1
return (x + 1) >> 1


• func minSwaps(s string) int {
x := 0
for _, c := range s {
if c == '[' {
x++
} else if x > 0 {
x--
}
}
return (x + 1) / 2
}

• function minSwaps(s: string): number {
let x = 0;
for (const c of s) {
if (c === '[') {
++x;
} else if (x) {
--x;
}
}
return (x + 1) >> 1;
}