class Solution {
public:
int minSwaps(string s) {
}
};
1963. 使字符串平衡的最小交换次数
给你一个字符串 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.length2 <= n <= 106n 为偶数s[i] 为'[' 或 ']''[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2原站题解
cpp 解法, 执行用时: 16 ms, 内存消耗: 33.3 MB, 提交时间: 2025-03-17 09:25:17
class Solution {
public:
int minSwaps(string s) {
int c = 0;
for (char b : s) {
if (b == '[' || c == 0) {
c++;
} else {
c--;
}
}
return c / 2;
}
};
java 解法, 执行用时: 17 ms, 内存消耗: 54.7 MB, 提交时间: 2025-03-17 09:25:06
class Solution {
public int minSwaps(String s) {
int c = 0;
for (char b : s.toCharArray()) {
if (b == '[' || c == 0) {
c++;
} else {
c--;
}
}
return c / 2;
}
}
rust 解法, 执行用时: 7 ms, 内存消耗: 4.7 MB, 提交时间: 2025-03-17 09:24:48
impl Solution {
pub fn min_swaps(s: String) -> i32 {
let mut c = 0;
for b in s.bytes() {
if b == b'[' || c == 0 {
c += 1;
} else {
c -= 1;
}
}
c / 2
}
}
javascript 解法, 执行用时: 31 ms, 内存消耗: 66.2 MB, 提交时间: 2025-03-17 09:24:36
/**
* @param {string} s
* @return {number}
*/
var minSwaps = function(s) {
let c = 0;
for (const b of s) {
if (b === '[' || c === 0) {
c++;
} else {
c--;
}
}
return c / 2;
};
golang 解法, 执行用时: 32 ms, 内存消耗: 8.5 MB, 提交时间: 2022-11-29 11:17:33
func minSwaps(s string) (ans int) {
c := 0
for _, b := range s {
if b == '[' {
c++
} else if c > 0 {
c--
} else {
c++ // 把最后面的 [ 和 ] 交换
ans++
}
}
return
}
python3 解法, 执行用时: 464 ms, 内存消耗: 19.6 MB, 提交时间: 2022-11-29 11:16:52
class Solution:
def minSwaps(self, s: str) -> int:
cnt = mincnt = 0
for ch in s:
if ch == '[':
cnt += 1
else:
cnt -= 1
mincnt = min(mincnt, cnt)
return (-mincnt + 1) // 2