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

🟠   🔖  栈 贪心 双指针 字符串  🔗 力扣 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	平衡括号字符串的最少插入次数		栈 贪心 字符串