1963.md

title	description	keywords
1963. 使字符串平衡的最小交换次数	LeetCode 1963. 使字符串平衡的最小交换次数题解，Minimum Number of Swaps to Make the String Balanced，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1963. 使字符串平衡的最小交换次数 使字符串平衡的最小交换次数 Minimum Number of Swaps to Make the String Balanced 解题思路 栈 贪心 双指针 字符串

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

🟠 Medium  🔖  栈 贪心 双指针 字符串  🔗 力扣 LeetCode

题目

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 theminimum 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 <= 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.

题目大意

给你一个字符串 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 <= 10^6
• n 为偶数
• s[i] 为'[' 或 ']'
• 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2

解题思路

当遍历字符串时，如果发现右括号 ] 的数量比左括号 [ 的数量多，这表示当前字符串已经不平衡了。此时，需要进行交换来修复这种不平衡。

在遍历字符串的过程中，可以维护一个变量 imbalance 来跟踪当前不平衡的右括号数量。

每次遇到不平衡的地方时，说明遇到了多余的右括，需要一个之后的左括号与右括号交换来减少 imbalance。每次交换可以平衡一对括号，因此总共需要的交换次数（即 imbalance 的最大值）就是字符串中的不平衡对数。

1. 初始化 imbalance 为 0，用于记录当前不平衡的右括号数量。
2. 遍历字符串中的每个字符：
   • 如果是左括号 [，则平衡增加，imbalance 减少。
   • 如果是右括号 ]，则不平衡增加，imbalance 增加。
3. 每次 imbalance 递增时，表示当前右括号过多，需要进行一次交换。
4. 遍历结束后，交换次数即为需要的最小交换次数。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需遍历一次字符串。
• 空间复杂度：O(1)，只需要常数空间来存储 imbalance 和 maxImbalance。

代码

/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function (s) {
	let imbalance = 0,
		maxImbalance = 0;

	for (let char of s) {
		if (char === '[') {
			imbalance--;
		} else {
			imbalance++;
		}
		// 记录最大不平衡
		maxImbalance = Math.max(maxImbalance, imbalance);
	}

	// 最小交换次数是最大不平衡的一半，向上取整
	return Math.ceil(maxImbalance / 2);
};

相关题目

题号	标题	题解	标签	难度	力扣
301	删除无效的括号		广度优先搜索 字符串 回溯	🔴	🀄️ 🔗
921	使括号有效的最少添加	[✓]	栈 贪心 字符串	🟠	🀄️ 🔗
1249	移除无效的括号		栈 字符串	🟠	🀄️ 🔗
1541	平衡括号字符串的最少插入次数		栈 贪心 字符串	🟠	🀄️ 🔗