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

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

力扣题目链接:https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-string-balanced/

给你一个字符串 s下标从 0 开始 ,且长度为偶数 n 。字符串 恰好n / 2 个开括号 '['n / 2 个闭括号 ']' 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串

  • 字符串是一个空字符串,或者
  • 字符串可以记作 AB ,其中 AB 都是 平衡字符串 ,或者
  • 字符串可以写成 [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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
* @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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
* @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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
* @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和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


1963.使字符串平衡的最小交换次数:计数模拟(不需要麻烦的“三种写法一步步优化”)
https://blog.letmefly.xyz/2025/03/17/LeetCode 1963.使字符串平衡的最小交换次数/
作者
Tisfy
发布于
2025年3月17日
许可协议