1963.使字符串平衡的最小交换次数：计数模拟(不需要麻烦的“三种写法一步步优化”)

【LetMeFly】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 <= 106
• n 为偶数
• s[i] 为'[' 或 ']'
• 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2

解题方法：计数模拟

题目保证[和]的数量是相同的，也就是说一定可以通过交换达成配对。

使用两个变量：$zuoQianYou$(左前右)和$zuo$分别记录“[前]”的数量和“未被消耗的[”的数量。

遍历字符串

• 如果当前字符是[，就说明后续可以有一个]来和它配对并将他“消费”，$zuo+=1$

• 如果当前字符是]，就看有无[以供配对：

  • 如果$zuo\gt 0$，说明有未配对的[，消耗之（$zuo-=1$）
  • 否则(没有未配对的[)，$zuoQianYou+=1$

存在“无法配对的[前]”就说明要发生交换。但是注意$zuoQianYou$个“[前]”只需要交换$\lceil\frac{zuoQianYou}{2}\rceil$次，因为]和后面某个[交换后，实际上[的数量也加一了，顺便就还能与一个]配对。

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

对于某“三种写法，一步步优化”，看似看完恍然大悟，实则完全没必要那么麻烦。因为这“一步步优化”实则大概是其作者的思考过程罢了。若能直接想到简单方法，就直接想吧！尝试几次就能发现之前想法可能存在的漏洞了。但不可否认这位作者绝大多数文章还是十分优质的。

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-03-17 12:16:25
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-17 12:17:39
 */
class Solution {
public:
    int minSwaps(string s) {
        int zuoQianYou = 0, zuo = 0;
        for (char c : s) {
            if (c == '[') {
                zuo++;
            } else {
                if (zuo) {
                    zuo--;
                } else {
                    zuoQianYou++;
                }
            }
        }
        return (zuoQianYou + 1) / 2;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-03-17 12:18:42
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-17 12:18:42
'''
class Solution:
    def minSwaps(self, s: str) -> int:
        zuoQianYou = zuo = 0
        for c in s:
            if c == '[':
                zuo += 1
            else:
                if zuo:
                    zuo -= 1
                else:
                    zuoQianYou += 1
        return (zuoQianYou + 1) // 2

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-03-17 12:21:49
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-17 12:21:49
 */
class Solution {
    public int minSwaps(String s) {
        int zuoQianYou = 0, zuo = 0;
        for (char c : s.toCharArray()) {
            if (c == '[') {
                zuo++;
            } else {
                if (zuo > 0) {
                    zuo--;
                } else {
                    zuoQianYou++;
                }
            }
        }
        return (zuoQianYou + 1) / 2;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-03-17 12:20:26
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-17 12:21:31
 */
package main

func minSwaps(s string) int {
    zuoQianYou, zuo := 0, 0
    for i := range s {
        if s[i] == '[' {
            zuo++
        } else {
            if zuo > 0 {
                zuo--
            } else {
                zuoQianYou++
            }
        }
    }
    return (zuoQianYou + 1) / 2
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源