M3714.最长的平衡子串 II

hash table, string, prefix sum, https://leetcode.cn/problems/longest-balanced-substring-ii/

给你一个只包含字符 'a'、'b' 和 'c' 的字符串 s。

如果一个 子串 中所有 不同 字符出现的次数都 相同，则称该子串为 平衡 子串。

请返回 s 的 最长平衡子串 的 长度 。

子串 是字符串中连续的、非空 的字符序列。

示例 1：

输入： s = "abbac"

输出： 4

解释：

最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 2 次。

示例 2：

输入： s = "aabcc"

输出： 3

解释：

最长的平衡子串是 "abc"，因为不同字符 'a'、'b' 和 'c' 都恰好出现了 1 次。

示例 3：

输入： s = "aba"

输出： 2

解释：

最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 1 次。另一个最长的平衡子串是 "ba"。

提示：

• 1 <= s.length <= 10^5
• s 仅包含字符 'a'、'b' 和 'c'。

题目要求在只包含 'a'、'b'、'c' 的字符串中找到最长的“平衡子串”。平衡子串的定义是：该子串中出现的所有不同字符的次数都相等。

解题思路

根据平衡子串的定义，子串中可能包含的不同字符集有 7 种情况：

1. 只有一个字符：{'a'}、{'b'} 或 {'c'}。
2. 只有两个字符：{'a', 'b'}、{'a', 'c'} 或 {'b', 'c'}。
3. 包含三个字符：{'a', 'b', 'c'}。

我们可以分别处理这三种情况：

1. 单字符子串：任何只由一种字符组成的连续序列都是平衡的（因为只有一种不同字符，且其出现次数自相等）。最长的此类子串即为字符串中最长的连续相同字符序列。
2. 双字符子串：例如对于字符集 {'a', 'b'}，子串必须包含 'a' 和 'b' 且不包含 'c'。
   • 处理方法：以 'c' 作为分隔符将字符串切分成若干段。在每一段内（只含 'a' 和 'b'），我们寻找满足 count('a') == count('b') 的最长子串。这可以使用前缀和之差的方法：维护 diff = count('a') - count('b')，当两个位置的 diff 相等时，说明中间这段的 'a' 和 'b' 数量相等。
3. 三字符子串：子串必须同时包含 'a'、'b'、'c' 且数量相等。
   • 处理方法：同样使用前缀和。维护两个差值：d1 = count('a') - count('b') 和 d2 = count('b') - count('c')。当两个位置的 (d1, d2) 元组相等时，说明中间这段的 a, b, c 增加量相同。

算法步骤

1. 初始化 ans = 0。
2. 处理单字符：遍历一遍字符串，记录当前连续相同字符的长度，更新 ans。
3. 处理双字符：针对三组对 (a,b,c), (a,c,b), (b,c,a)，使用 split(other) 分段，在每段内用哈希表记录 diff 第一次出现的索引，计算最长平衡长度。
4. 处理三字符：在全串上维护 (count(a)-count(b), count(b)-count(c)) 的哈希表，记录第一次出现的索引，更新 ans。

代码实现

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        ans = 0
        
        # 1. 处理单字符子串（如 "aaaa"）
        if n > 0:
            cur_len = 1
            for i in range(1, n):
                if s[i] == s[i-1]:
                    cur_len += 1
                else:
                    ans = max(ans, cur_len)
                    cur_len = 1
            ans = max(ans, cur_len)

        # 2. 处理双字符子串（如 "aabb"）
        # 分别考虑 {a,b}, {a,c}, {b,c} 三种组合
        for c1, c2, other in [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'c', 'a')]:
            # 通过 other 字符切割，保证段内只有 c1 和 c2
            for seg in s.split(other):
                if not seg: continue
                # 在段内找 count(c1) == count(c2) 的最长子串
                first = {0: -1}
                diff = 0
                for i, char in enumerate(seg):
                    if char == c1:
                        diff += 1
                    else: # char == c2
                        diff -= 1
                    
                    if diff in first:
                        # 如果 diff 相同，说明中间 c1 和 c2 增加量相同
                        # 且由于段内只有这两种字符，长度 > 0 意味着两种字符都出现了
                        ans = max(ans, i - first[diff])
                    else:
                        first[diff] = i

        # 3. 处理三字符子串（如 "abcabc"）
        # 维护两个差值状态 (cnt_a - cnt_b, cnt_b - cnt_c)
        first_tri = {(0, 0): -1}
        da, db = 0, 0
        for i, char in enumerate(s):
            if char == 'a':
                da += 1
            elif char == 'b':
                da -= 1
                db += 1
            else: # char == 'c'
                db -= 1
            
            state = (da, db)
            if state in first_tri:
                # 若状态相同，则 a, b, c 增加量 delta 相等
                # 若 i > first_tri[state]，则 delta 必然 > 0
                ans = max(ans, i - first_tri[state])
            else:
                first_tri[state] = i
                    
        return ans

复杂度分析

• 时间复杂度：$O(n)$。我们对字符串进行了有限次数（约 5 次）的线性扫描。哈希表的操作平均为 $O(1)$。
• 空间复杂度：$O(n)$。主要用于存储 split 产生的中间字符串和哈希表的状态记录。在 $n={10}^5$ 的量级下，内存占用在可接受范围内。

这段代码的核心逻辑是利用“前缀和+哈希表”的技巧来寻找只包含两种特定字符且这两者数量相等的最长子串。

下面我通过三个层面来拆解这段代码：

1. 为什么要用 s.split(other)？

题目要求子串中的“所有不同字符”次数相同。如果我们现在想找只包含 'a' 和 'b' 的平衡子串，那么这个子串里绝对不能出现 'c'。

• s.split('c') 会把原字符串按照 'c' 切开，得到若干个只包含 'a' 和 'b' 的片段（seg）。
• 在这些片段里找 count('a') == count('b') 的子串，就能保证这个子串里只有两种字符，且它们数量相等。

2. diff 和 first 的逻辑（核心算法）

这是一个经典的算法技巧，用于寻找“和为 0”的最长连续子段。

• 变量定义：
  • diff：记录到当前位置为止，c1 出现的次数减去 c2 出现的次数。
  • first (哈希表)：记录某个 diff 值第一次出现时的索引。
• 数学原理：
  • 假设在索引 $i$ 时，$diff=5$；在后面某个索引 $j$ 时，$diff$ 又是 $5$。
  • 这意味着从 $i+1$ 到 $j$ 这一段区间内，c1 增加的次数和 c2 增加的次数抵消了（即这一段里 c1 和 c2 数量相等）。
  • 为了让子串最长，当再次遇到同一个 diff 时，我们用当前索引 $j$ 减去它第一次出现的索引 $first[diff]$。

3. 举个例子

假设 seg = "aabb"，我们要找 'a' 和 'b' 数量相等的子串：

1. 初始化：first = {0: -1}，diff = 0。
   • 意义：在还没开始遍历时（索引为 -1），diff 就是 0。
2. i = 0, char = 'a'：
   • diff 变成 1。
   • 1 不在 first 里，记录 first[1] = 0。
3. i = 1, char = 'a'：
   • diff 变成 2。
   • 2 不在 first 里，记录 first[2] = 1。
4. i = 2, char = 'b'：
   • diff 变成 1（因为 $2-1=1$）。
   • 1 已经在 first 里了（first[1] = 0）。
   • 此时长度 = i - first[1] = 2 - 0 = 2。对应子串 "ab"（从索引 1 到 2）。
5. i = 3, char = 'b'：
   • diff 变成 0（因为 $1-1=0$）。
   • 0 已经在 first 里了（first[0] = -1）。
   • 此时长度 = i - first[0] = 3 - (-1) = 4。对应子串 "aabb"。

补充说明

• 为什么 if not seg: continue？ 如果字符串是 "abc"，用 'b' 切分会得到 ["a", "c"]。如果字符串是 "aa...bb" 这种只有两类字符的，切分出来的片段可能为空，需要跳过。
• 为什么这段代码不处理 "aaaa"？ 如果片段里只有 'a'，diff 会一直增加（1, 2, 3...），永远不会出现重复的 diff，所以 ans 不会在这个循环里更新。单种字符的情况是由代码的第一部分（处理单字符连续长度）解决的。

总结： 这一段代码是在“排除掉第三种字符”的干扰后，利用前缀和之差，快速锁定两个字符数量相等的区间。

这段代码是处理包含三种字符（'a'、'b'、'c'）且它们数量全部相等的最长子串。它使用的依然是“前缀和+哈希表”的思想，只不过由于字符变成了三个，我们需要同时维护两个差值来锁定状态。

1. 数学原理

设从字符串开头到当前位置 $i$，'a' 出现的次数为 $N_a(i)$，'b' 为 $N_b(i)$，'c' 为 $N_c(i)$。

对于一个从 $j+1$ 到 $i$ 的子串，如果它是平衡的（且包含三种字符），则需要满足：

$$(N_a(i)-N_a(j))=(N_b(i)-N_b(j))=(N_c(i)-N_c(j))=k(k>0)$$

我们将这个等式拆解为两个独立的条件：

1. $N_a(i)-N_a(j)=N_b(i)-N_b(j)$ $⟹$ $N_a(i)-N_b(i)=N_a(j)-N_b(j)$
2. $N_b(i)-N_b(j)=N_c(i)-N_c(j)$ $⟹$ $N_b(i)-N_c(i)=N_b(j)-N_c(j)$

结论： 只要 $ (N_a - N_b) $ 和 $ (N_b - N_c) $ 这两个差值在 $i$ 点和 $j$ 点完全相同，那么 $j+1$ 到 $i$ 这一段中，'a', 'b', 'c' 增加的数量就一定是相等的。

---

2. 代码逻辑拆解

• da 和 db 的更新：
  • 当遇到 'a'：da += 1。此时 $(N_a-N_b)$ 变大。
  • 当遇到 'b'：da -= 1 且 db += 1。
    • da -= 1 是因为 $N_b$ 在分母/减数位置，$(N_a-N_b)$ 变小。
    • db += 1 是因为 $N_b$ 在分子/被减数位置，$(N_b-N_c)$ 变大。
  • 当遇到 'c'：db -= 1。此时 $(N_b-N_c)$ 变小。
• state = (da, db)： 我们将这两个差值组合成一个元组（Tuple）作为哈希表的键。
• first_tri = {(0, 0): -1}： 记录每种状态第一次出现的下标。初始状态 $(0,0)$ 发生在下标 $-1$。

---

3. 举例：s = "abcabc"

步骤 (i)	字符	da (a-b)	db (b-c)	状态 (da, db)	哈希表记录	结果 ans
初始		0	0	(0, 0)	{(0,0): -1}	0
0	a	1	0	(1, 0)	{(0,0):-1, (1,0):0}	0
1	b	0	1	(0, 1)	{(0,0):-1, (1,0):0, (0,1):1}	0
2	c	0	0	(0, 0)	命中！2 - (-1) = 3	3 (子串"abc")
3	a	1	0	(1, 0)	命中！3 - 0 = 3	3
4	b	0	1	(0, 1)	命中！4 - 1 = 3	3
5	c	0	0	(0, 0)	命中！5 - (-1) = 6	6 (子串"abcabc")

---

4. 为什么这段代码能同时处理单、双、三字符？

其实这种“多维差值”的逻辑非常强大：

1. 如果子串只有 'a' 和 'b' 相等： 在这一段内，$N_c$ 没变，所以 $db$ 会发生变化，导致 (da, db) 状态和之前的对不上。因此，这段代码主要负责找三种字符数量都相等的情况。
2. 那只有两类字符相等怎么办？ 这就是为什么我们在代码的前一部分（s.split(other) 那里）专门写了处理两个字符逻辑的原因。
3. 那单字符怎么办？ 由代码最开始的连续字符统计逻辑处理。

总结

这段代码通过维护一个二维坐标 (a-b, b-c)。只要当前坐标回到了之前走过的某个位置，就说明刚才走过的那段路径里，a、b、c 的步数是完全一样的。这是解决这类“多种元素数量相等”问题的标准最优解法（时间复杂度 $O(N)$）。