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

难度: Medium

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

Submission

运行时间: 152 ms

内存: 22.0 MB

class Solution:
    def minSwaps(self, s: str) -> int:
        cnt = 0
        for ch in s:
            if ch == ']' and cnt > 0:
                cnt -= 1
            else:
                cnt += 1
        return cnt // 2

Explain

此题解采用贪心算法的思路来解决问题。首先初始化一个计数器 cnt 来记录遇到的未匹配的 ']' 的数量。遍历字符串，每次遇到 ']' 且 cnt 大于 0 时，说明前面有一个 '[' 可以与之匹配，因此将 cnt 减一。如果遇到 '[' 或者 cnt 为 0 时遇到 ']'，则 cnt 加一。最后，cnt 表示的是无法匹配的 '[' 的数量（每个这样的 '[' 都需要一个对应的 ']' 来匹配以平衡字符串）。因此，需要的最小交换次数为 cnt 的一半，因为每一次交换可以解决两个未匹配的括号。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minSwaps(self, s: str) -> int:
        cnt = 0  # 初始化计数器，用于记录未匹配的 ']' 数量
        for ch in s:  # 遍历字符串中的每个字符
            if ch == ']' and cnt > 0:  # 如果当前字符是 ']' 且存在未匹配的 '['
                cnt -= 1  # 匹配一个 '[' 和当前的 ']'
            else:  # 如果当前字符是 '[' 或遇到 ']' 但没有未匹配的 '['
                cnt += 1  # 增加未匹配的括号计数
        return cnt // 2  # 每两个未匹配的括号通过一次交换可以被匹配，因此返回 cnt 的一半

Explore

在算法中，'未匹配的 ] 的数量'是指在遍历字符串时，遇到的']'字符，但在它之前没有足够的'['字符可以与之配对的次数。这是一个负载计数，用于追踪需要额外'['来平衡的']'的数量。当遇到'['时，我们暂时认为它是多余的，因为此时尚未遇到可以与之匹配的']'，所以将cnt增加。这种做法是为了后续遇到']'时，能够用这些'['进行匹配。实际上，cnt在这里计数的是未匹配的括号数量，正负号表示未匹配的类型（正表示'['，负表示']'）。

是的，当cnt大于0且遇到']'时，cnt减一的操作确实意味着前面有一个未匹配的'['可以与之配对。cnt大于0表示在这个位置之前，有未匹配的'['存在（即'['的数量多于']'的数量）。因此，遇到']'可以与之前一个'['配对，从而减少未匹配的'['的数量，也就是cnt减一。

最终返回cnt的一半是因为每次交换可以解决两个未匹配的括号。具体来说，如果有两个未匹配的括号（例如两个'['），那么通过将其中一个'['与后面某个']'交换位置，可以让两个'['都找到各自的匹配']'。这意味着每进行一次交换，就有两个未匹配的括号被匹配掉。因此，未匹配括号的总数（即cnt）除以2就是需要的最小交换次数。