原文链接: https://leetcode-cn.com/problems/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 变成 平衡字符串 所需要的 最小 交换次数。

 

示例 1：

输入：s = "][]["
输出：1
解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
最终字符串变成 "[[]]" 。

示例 2：

输入：s = "]]][[["
输出：2
解释：执行下述操作可以使字符串变成平衡字符串：
- 交换下标 0 和下标 4 对应的括号，s = "[]][][" 。
- 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
最终字符串变成 "[[][]]" 。

示例 3：

输入：s = "[]"
输出：0
解释：这个字符串已经是平衡字符串。

 

提示：

• n == s.length
• 2 <= n <= 106
• n 为偶数
• s[i] 为'[' 或 ']'
• 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2

通过代码

高赞题解

对于一个平衡字符串，从左往右遍历它，统计未匹配的左括号的个数 $c$，遇到左括号就加一，遇到右括号就减一，如果任何时刻 $c$ 都不为负数，那么这个字符串就是平衡的。

如果遍历时遇到右括号并且此时 $c=0$，那么就需要在后面找一个左括号并与这个右括号交换。

为了使后续的交换次数最小，这个被交换走的右括号应当越靠右越好，所以我们可以拿字符串最右边的左括号来交换。

实际代码中，可以不用编写「交换」的逻辑，这是因为我们总是选择最右边的左括号，因此在后续的遍历中，若遇到了这些左括号，在交换后的字符串上，该位置及后面必然全部是右括号，即此时该字符串已经是平衡的了。

因此，当遇到右括号并且此时 $c=0$，可以直接将 $c$ 和答案加一，即视作将一个左括号和该右括号交换。由于没有实际交换括号，若后面又重新遇到了需要被交换的左括号，由于此时字符串已经是平衡的了，故不会对答案产生影响。

func minSwaps(s string) (ans int) {
	c := 0
	for _, b := range s {
		if b == '[' {
			c++
		} else if c > 0 {
			c--
		} else {
			c++ // 把最后面的 [ 和 ] 交换
			ans++
		}
	}
	return
}

统计信息

通过次数	提交次数	AC比率
4661	7535	61.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言