[LeetCode] 1963. Minimum Number of Swaps to Make the String Balanced

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.

使字符串平衡的最小交换次数。

给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串 ：

字符串是一个空字符串，或者
字符串可以记作 AB ，其中 A 和 B 都是 平衡字符串 ，或者
字符串可以写成 [C] ，其中 C 是一个 平衡字符串 。
你可以交换 任意 两个下标所对应的括号 任意 次数。

返回使 s 变成 平衡字符串 所需要的 最小 交换次数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-swaps-to-make-the-string-balanced
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

因为是括号配对类型的题目，所以思路不难想到是 stack 这一类的。遇到左括号就入栈；遇到右括号，看看栈顶元素是否是左括号，如果是，就抵消左括号。注意这道题说了字符串 恰好 由 n / 2 个开括号 ‘[‘ 和 n / 2 个闭括号 ‘]’ 组成，所以无需处理左右括号数量不等的情况。

复杂度

时间O(n)
空间O(n)

代码一 - stack

Java实现

class Solution {
    public int minSwaps(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '[') {
                stack.push(c);
            } else {
                if (!stack.isEmpty() && stack.peekLast() == '[') {
                    stack.pop();
                }
            }
        }
        return (stack.size() + 1) / 2;
    }
}

代码二，无需 stack，只统计匹配不上的括号数

Java实现

class Solution {
	public int minSwaps(String s) {
		int size = 0;
		for (char c : s.toCharArray()) {
			if (c == '[') {
				size++;
			} else {
				// 必有左括号出现过了，可以抵消
				if (size > 0) {
					size--;
				}
			}
		}
		return (size + 1) / 2;
	}
}