[LeetCode] 每日一题 1963. 使字符串平衡的最小交换次数

题目链接

https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-string-balanced

题目描述

给你一个字符串 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

解题思路

本题要求通过最小交换次数将字符串变为平衡字符串。由于交换可以发生在任意两个位置，我们可以贪心地尽量让右括号 ] 及时匹配到左括号 [，从而减少后续的交换次数

我们使用一个 cnt 变量来记录当前未匹配的左括号 [ 数量：

• 遍历字符串时，遇到 [，cnt 加一，表示新增一个未匹配的左括号

• 遇到 ] 时，如果 cnt > 0，说明可以匹配 [，因此 cnt 减一

• 如果 cnt == 0 但仍然遇到了 ]，说明此时 ] 需要通过交换来匹配一个 [，因此我们将 ans（交换次数）加一，并假设执行交换后 cnt 继续保持正数，以匹配后续的括号

最终，ans 即为最小交换次数

代码实现

class Solution {
    public int minSwaps(String s) {
        int cnt = 0;
        int ans = 0;
        for (char c : s.toCharArray()) {
            if (c == '[') {
                cnt++;
            } else if (cnt > 0) {
                cnt--;
            } else {
                ans++;
                cnt++;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，遍历字符串一次即可完成计算

• 空间复杂度：O(1)，只使用了两个额外的整数变量 cnt 和 ans，不会额外占用空间

总结

本题利用贪心算法，通过计数未匹配的左括号数量，确保右括号 ] 尽早匹配，从而最小化交换次数。核心思想是当 ] 无法匹配时，执行交换，使 ] 能够匹配一个 [。这是一种典型的局部最优 -> 全局最优的贪心策略

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。