Formatted question description: https://leetcode.ca/all/1963.html

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

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:1Explanation:You can make the string balanced by swapping index 0 with index 3. The resulting string is "[[]]".

**Example 2:**

Input:s = "]]][[["Output:2Explanation: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:0Explanation:The string is already balanced.

**Constraints:**

`n == s.length`

`2 <= n <= 10`

^{6}`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`

.

**Companies**:

Amazon

**Related Topics**:

Two Pointers, String, Stack, Greedy

**Similar Questions**:

- Remove Invalid Parentheses (Hard)
- Minimum Add to Make Parentheses Valid (Medium)
- Minimum Remove to Make Valid Parentheses (Medium)
- Minimum Insertions to Balance a Parentheses String (Medium)

## Solution 1. Two Pointers

**Intuition**: We keep looking for the first unmatched `]`

from left and the first unmatched `[`

from the right, and swap them.

**Algorithm**: Use two pointers `L = 0, R = N - 1`

, and two counters `left`

and `right`

which are the number of unmatched `[`

/`]`

from left/right, respectively. For example, if we’ve seen `[[]`

from the left, then `left = 1`

because there is one `[`

unmatched.

We keep incrementing `L`

and decrementing `R`

until `left`

and `right`

become `-1`

. And we swap `s[L]`

and `s[R]`

and set `left = right = 1`

.

```
// OJ: https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minSwaps(string s) {
int left = 0, right = 0, N = s.size(), L = 0, R = N - 1, ans = 0;
while (L < R) {
for (; L < R; ++L) {
left += s[L] == '[' ? 1 : -1;
if (left == -1) break;
}
if (L >= R) break; // no more unmatched branchets, break
for (; L < R; --R) {
right += s[R] == ']' ? 1 : -1;
if (right == -1) break;
}
left = right = 1; // after swapping `s[L]` and `s[R]`, `left` and `right` will become `1`.
++L, --R;
++ans;
}
return ans;
}
};
```

## Solution 2. Two Pointers

Find the first unmatched `]`

from the left, and swap it with the first `[`

from the right.

```
// OJ: https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minSwaps(string s) {
int N = s.size(), cnt = 0, j = N - 1, ans = 0;
for (int i = 0; i < j; ++i) {
cnt += s[i] == '[' ? 1 : -1;
if (cnt == -1) { // found an unmatched `]`
while (s[j] == ']') --j; // swap with the rightmost `[`
cnt = 1;
++ans;
}
}
return ans;
}
};
```

## Solution 3. Math

We can discard all the balanced components first. The remaining string must be in this form

```
]]]]...[[[[...
```

The optimal approach is to balance 2 sets of brackets at a time using 1 swap.

For example:

```
]]]]]][[[[[[
// swap 1
v v
]]]][][][[[[
// swap 2
v v
]][][][][][[
// swap 3
v v
[][][][][][]
```

We can write the number of mismatches and the corresponding optimal swaps

```
mismatches = 0, 1, 2, 3, 4, 5, 6, ...
swaps = 0, 1, 1, 2, 2, 3, 3, ...
```

We can see the pattern is `swaps = (mismatches + 1) / 2`

.

```
// OJ: https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minSwaps(string s) {
int N = s.size(), cnt = 0, mismatch = 0;
for (char c : s) {
if (c == '[') ++cnt;
else if (cnt > 0) --cnt;
else ++mismatch;
}
return (mismatch + 1) / 2;
}
};
```