What is the minimum number of swaps to make a string balanced?

It is the count of times the running imbalance of brackets drops below zero during a single pass through the string.

Can this problem be solved using a stack?

Yes, a stack can track unmatched brackets, but a counter for imbalance is more space-efficient for this exact problem.

Why does the two-pointer scanning pattern work here?

It efficiently locates mismatched brackets and determines swaps by tracking the running imbalance without extra storage.

What is the time and space complexity?

Time is O(n) as each character is processed once, and space is O(1) using only counters.

Does the string need to be preprocessed before applying the algorithm?

No preprocessing is needed; iterate directly while counting the imbalance and apply swaps virtually as required.

#1963

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

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

给你一个字符串 s ，下标从 0 开始，且长度为偶数 n 。字符串恰好由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。只有能满足下述所有条件的字符串才能称为平衡字符串：字符串是一个空字符串，或者字符串可以记作 AB ，其中 A 和 B 都是平衡字符串，…

双指针字符串栈贪心

题目描述

给你一个字符串 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⁶
n 为偶数
s[i] 为'[' 或 ']'
开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2

lightbulb

解题思路

方法一：贪心

我们用一个变量 $x$ 记录当前未匹配的左括号的数量，遍历字符串 $s$ ，对于每个字符 $c$ ：

如果 $c$ 是左括号，那么 $x$ 加一；
如果 $c$ 是右括号，那么我们需要判断 $x$ 是否大于零，如果大于零，那么将当前右括号与左侧最近的一个未匹配的左括号匹配，即 $x$ 减一。

遍历结束后，得到的一定是形如 "]]]...[[[..."的字符串，我们再贪心地每次将两端的括号交换，这样一次可以消去 $2$ 个不匹配的左括号。因此，一共需要交换的次数为 $\left\lfloor \frac{x + 1}{2} \right\rfloor$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minSwaps(self, s: str) -> int:
        x = 0
        for c in s:
            if c == "[":
                x += 1
            elif x:
                x -= 1
        return (x + 1) >> 1

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is processed once during scanning. Space complexity is O(1) since only counters and a few variables are used, no extra arrays or stacks are required.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Do you track the imbalance during iteration or attempt all swap combinations?
question_mark
Can you optimize space by avoiding explicit swaps and using counters?
question_mark
How do you determine the exact moment a swap is necessary in a single pass?

warning

常见陷阱

外企场景

error
Forgetting to reset the imbalance counter after each necessary swap, leading to incorrect totals.
error
Assuming swaps can be minimized by pairing only adjacent brackets rather than using imbalance tracking.
error
Using extra stacks or arrays unnecessarily, increasing space complexity beyond O(1).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute minimum swaps to balance strings with multiple types of brackets using a generalized two-pointer invariant.
arrow_right_alt
Count the number of swaps required if only adjacent bracket swaps are allowed, requiring more careful tracking.
arrow_right_alt
Determine maximum balanced prefix length after performing at most k swaps, applying similar imbalance tracking.

help

常见问题

外企场景

继续练习

#2000 反转单词前缀 #2030 含特定字母的最小子序列 #1850 邻位交换的最小次数