题目

给你一个只包含字符 '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' 三种）。

我们需要考虑以下三种情况的“平衡子串”：

1. 子串中只包含 1 种字符

这种情况非常简单。如果子串只有 'a'，那么它一定是平衡的（因为唯一的不同字符出现的次数就是它本身的长度）。

• 策略：直接遍历字符串，统计最长的连续相同字符的长度。

2. 子串中包含 2 种字符 (例如 'a' 和 'b')

我们要找一个不包含 'c' 的子串，且其中 'a' 的数量等于 'b' 的数量。

• 转化：我们将 'c' 视为“隔断/墙壁”。每当遇到 'c'，当前的计数和哈希表需要重置，因为子串不能跨越 'c'。
• 数学模型：对于 'a' 和 'b' 的子段，我们寻找 $Count(a) = Count(b)$。这等价于 $Count(a) - Count(b) = 0$。
• 技巧：使用前缀和差值。
  • 维护变量 diff = count_a - count_b。
  • 使用哈希表记录每个 diff 第一次出现的索引。
  • 当同一个 diff 再次出现时，说明两个索引之间的子串满足 'a' 和 'b' 数量增加量相同（即增量相等），此时更新最大长度。
  • 我们需要对三种组合分别做一次遍历：('a', 'b'), ('a', 'c'), ('b', 'c')。

3. 子串中包含 3 种字符 ('a', 'b', 'c')

我们要找一个子串，其中 $Count(a) = Count(b) = Count(c)$。

• 转化：这等价于 $Count(a) - Count(b) = 0$ 且 $Count(b) - Count(c) = 0$。
• 技巧：同样使用前缀和，但这次状态是一个二元组。
  • 状态 Key：(count_a - count_b, count_b - count_c)。
  • 如果当前索引 $i$ 的状态与之前索引 $j$ 的状态相同，说明在区间 $(j, i]$ 内，a、b、c 增加的数量完全一致。
  • 注意：这里不需要“隔断”，因为我们本身就在寻找包含所有三种字符的情况。

具体代码

func longestBalanced(s string) int {
    n := len(s)
    ans := 0

    // 辅助函数：求最大值
    max := func(a, b int) int {
        if a > b {
            return a
        }
        return b
    }

    // ---------------------------------------------------------
    // 情况 1: 子串中只包含 1 种字符 (例如 "aaaa")
    // ---------------------------------------------------------
    currentLen := 0
    for i := 0; i < n; i++ {
        if i > 0 && s[i] == s[i-1] {
            currentLen++
        } else {
            currentLen = 1
        }
        ans = max(ans, currentLen)
    }

    // ---------------------------------------------------------
    // 情况 2: 子串中只包含 2 种字符 (例如 a和b, 禁止c)
    // ---------------------------------------------------------
    // 定义闭包函数处理两两组合
    checkTwo := func(c1, c2, forbidden byte) {
        // diffMap 存储 { (count1 - count2) : 第一次出现的索引 }
        // 初始状态：差值为0，虚拟索引为 -1
        diffMap := map[int]int{0: -1}
        diff := 0 // 维护 c1 的数量 - c2 的数量

        for i := 0; i < n; i++ {
            char := s[i]
            if char == forbidden {
                // 遇到禁字：重置状态。
                // 当前位置 i 成为新的“虚拟起点”（相当于新的 -1）
                diffMap = map[int]int{0: i}
                diff = 0
            } else {
                if char == c1 {
                    diff++
                } else if char == c2 {
                    diff--
                }

                // 检查当前差值是否之前出现过
                if firstIdx, ok := diffMap[diff]; ok {
                    ans = max(ans, i-firstIdx)
                } else {
                    diffMap[diff] = i
                }
            }
        }
    }

    // 检查三种组合：(a,b 禁c), (a,c 禁b), (b,c 禁a)
    checkTwo('a', 'b', 'c')
    checkTwo('a', 'c', 'b')
    checkTwo('b', 'c', 'a')

    // ---------------------------------------------------------
    // 情况 3: 子串中包含 3 种字符 (a, b, c)
    // ---------------------------------------------------------
    // 策略：寻找 a=b=c，即 (a-b)=0 且 (b-c)=0
    // stateMap Key: [2]int{a-b, b-c}
    
    // 初始状态：两个差值都是0，虚拟索引 -1
    stateMap := map[[2]int]int{{0, 0}: -1}
    a, b, c := 0, 0, 0

    for i := 0; i < n; i++ {
        char := s[i]
        if char == 'a' {
            a++
        } else if char == 'b' {
            b++
        } else if char == 'c' {
            c++
        }

        // 将两个差值作为状态 Key
        currentState := [2]int{a - b, b - c}

        if firstIdx, ok := stateMap[currentState]; ok {
            ans = max(ans, i-firstIdx)
        } else {
            stateMap[currentState] = i
        }
    }

    return ans
}