1963

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: 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.

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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
    }
};