2026-03-08：最长的平衡子串Ⅱ。用go语言，给定一个仅由字符 ‘a‘、‘b‘、‘c‘ 组成的字符串 s。我们把任意连续且非空的一段字符称为

福大大架构师每日一题

发布于 2026-03-09 12:57:31

680

2026-03-08：最长的平衡子串Ⅱ。用go语言，给定一个仅由字符 'a'、'b'、'c' 组成的字符串 s。我们把任意连续且非空的一段字符称为子串；若该子串中出现的每一种字母出现次数相等，则称其为“平衡子串”。请找出 s 中最长的平衡子串，并返回其长度。

1 <= s.length <= 100000。

s 仅包含字符 'a'、'b' 和 'c'。

输入： s = "abbac"。

输出： 4。

解释：

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

题目来自力扣3714。

一、整体解题思路概述

针对“最长的平衡子串Ⅱ”问题（仅含a/b/c的字符串，找最长连续子串满足所有出现的字母频次相等），采用分情况讨论 + 前缀和+哈希表优化的思路，核心是将原问题拆解为三种场景分别求解，最终取最大值，避免了暴力枚举的高时间复杂度，适配题目中字符串长度达10^5的要求。

二、分步骤详细执行过程

步骤1：处理“情况一：子串仅包含一种字符”

这个场景的核心逻辑是：仅含一种字符的子串天然满足“所有出现的字母频次相等”（只有一种字母，频次必然相同），需要找到这类子串的最长长度。

1. 初始化变量last为0，用于记录当前连续相同字符的长度；初始化结果res为0，记录全局最长长度。
2. 遍历字符串的每个字符（索引i从0到n-1）：
- • 若当前字符s[i]和前一个字符s[i-1]相同（i>0），说明连续相同字符的长度可以延续，last加1；
- • 若当前字符和前一个不同（或i=0），说明新的连续相同字符段开始，重置last为1；
- • 每次更新last后，比较last和res，将res更新为两者中的较大值（确保res始终是当前找到的最长单字符子串长度）。
3. 以输入s="abbac"为例：
- • i=0（字符a）：last=1，res=1；
- • i=1（字符b）：和前一个a不同，last=1，res仍为1；
- • i=2（字符b）：和前一个b相同，last=2，res更新为2；
- • i=3（字符a）：和前一个b不同，last=1，res仍为2；
- • i=4（字符c）：和前一个a不同，last=1，res仍为2；此步骤结束后，res=2（最长单字符子串是"bb"，长度2）。

步骤2：处理“情况二：子串包含两种字符”

这个场景的核心逻辑是：找到仅由a&b、b&c、a&c两两组合构成的子串中，满足两种字符频次相等的最长子串，通过case2Helper函数实现，且会分别验证这三组字符组合。以case2Helper(s, x, y)（比如x='a'、y='b'）为例，详细执行过程：

1. 函数初始化结果res=0，遍历字符串每个位置i：
- • 跳过非x、非y的字符（只关注由x和y组成的子串段）；
- • 若当前字符是x或y，初始化哈希表h（记录“差值diff”对应的最早索引），先存入h[0] = i-1（差值为0的初始位置，处理从i开始的子串）；
- • 初始化diff=0（表示x和y的数量差值，x出现+1，y出现-1），j从i开始遍历：
  - • 仅遍历连续的x/y字符段（遇到非x/y则停止）；
  - • 若s[j] == x，diff++；若s[j] == y，diff--；
  - • 检查哈希表h中是否存在当前diff：
    - • 若存在：说明从h[diff]+1到j的子串中，x和y的数量差值为0（即数量相等），计算子串长度j - h[diff]，若大于当前res则更新res；
    - • 若不存在：将当前diff和索引j存入h（只存首次出现的索引，保证后续能找到最长子串）；
  - • j自增，直到跳出x/y连续段；
- • 将i更新为j-1（跳过已处理的x/y段，减少循环次数）。
2. 分别调用case2Helper(s, 'a','b')、case2Helper(s, 'b','c')、case2Helper(s, 'a','c')：
- • 以case2Helper(s, 'a','b')为例（输入"abbac"）：
  - • i=0（字符a，属于a/b）：
    - • 初始化h[0]=-1，diff=0，j=0开始遍历：
    - • j=0（a）：diff=1，h中无1，存入h[1]=0；
    - • j=1（b）：diff=0，h中有0（对应索引-1），子串长度1 - (-1)=2，res=2；
    - • j=2（b）：diff=-1，h中无-1，存入h[-1]=2；
    - • j=3（a）：diff=0，h中有0（对应索引-1），子串长度3 - (-1)=4，res=4；
    - • j=4（c，非a/b）：停止遍历；
  - • 最终case2Helper(s, 'a','b')返回4，更新全局res为4；
- • 调用case2Helper(s, 'b','c')和case2Helper(s, 'a','c')返回的结果均小于4，全局res保持4。

步骤3：处理“情况三：子串包含三种字符”

这个场景的核心逻辑是：找到同时包含a、b、c三种字符，且三者频次相等的最长子串，通过“双差值+哈希表”记录前缀状态：

1. 定义结构体Key（包含x和y两个整数），用于记录“a-b的差值”和“b-c的差值”；
2. 初始化哈希表h，存入初始状态Key{n, n}: -1（n是字符串长度，用于避免差值为负的索引问题，初始位置为-1）；
3. 初始化diffAB=0（a和b的数量差值：a出现-1，b出现+1）、diffBC=0（b和c的数量差值：b出现+1，c出现-1）；
4. 遍历字符串每个索引i：
- • 根据当前字符更新差值：
  - • 字符为a：diffAB--（a多一个，a-b差值减1）；
  - • 字符为b：diffAB++（b多一个，a-b差值加1）且diffBC++（b多一个，b-c差值加1）；
  - • 字符为c：diffBC--（c多一个，b-c差值减1）；
- • 构造Key：Key{diffAB + n, diffBC + n}（加n避免负数，保证哈希表键为正）；
- • 检查哈希表h中是否存在该Key：
  - • 若存在：说明从h[Key]+1到i的子串中，a、b、c的数量相等（因为diffAB和diffBC均回到之前的状态，即三者差值未变，数量相等），计算子串长度i - h[Key]，若大于res则更新；
  - • 若不存在：将该Key和索引i存入h；
5. 以输入"abbac"为例：
- • 遍历过程中，所有Key均为首次出现，无满足条件的子串，因此res仍保持4（无三种字符频次相等的子串）。

步骤4：返回最终结果

经过三种情况的遍历和计算，全局res最终为4，即最长平衡子串的长度。

三、时间复杂度与空间复杂度分析

1. 时间复杂度

• 情况一：遍历字符串一次，时间复杂度O(n)；
• 情况二：三次调用case2Helper（a&b、b&c、a&c），每个case2Helper内部遍历字符串一次（跳过非目标字符，实际总遍历次数仍为O(n)），因此情况二总时间复杂度O(n)；
• 情况三：遍历字符串一次，时间复杂度O(n)；
• 总时间复杂度：O(n) + O(n) + O(n) = O(n)（n为字符串长度），适配10^5级别的输入规模。

2. 额外空间复杂度

• 情况一：仅使用少量变量（last、res），空间复杂度O(1)；
• 情况二：case2Helper中哈希表h的最大存储量为O(n)（最坏情况每个索引的差值都不同），三次调用的哈希表总空间仍为O(n)；
• 情况三：哈希表h存储Key和索引，最大存储量为O(n)；
• 总额外空间复杂度：O(n)（主要由哈希表的存储开销决定）。

总结

1. 核心流程：将问题拆解为“单字符、两字符、三字符”三种场景，分别用“连续计数”“差值+哈希表”“双差值+哈希表”求解，最终取最大值；
2. 关键优化：通过哈希表记录差值的首次出现索引，将子串频次相等的验证转化为“差值是否重复”，避免暴力枚举所有子串，将时间复杂度从O(n²)降至O(n)；
3. 复杂度：总时间复杂度为O(n)，总额外空间复杂度为O(n)（n为字符串长度）。

Go完整代码如下：

package main

import (
    "fmt"
)

func case2Helper(s string, x, y byte)int {
    n := len(s)
    res := 0

    for i := 0; i < n; i++ {
        if s[i] != x && s[i] != y {
            continue
        }

        h := make(map[int]int)
        h[0] = i - 1
        diff := 0
        j := i
        for j < n && (s[j] == x || s[j] == y) {
            if s[j] == x {
                diff++
            } else {
                diff--
            }

            if prev, exists := h[diff]; exists {
                if j-prev > res {
                    res = j - prev
                }
            } else {
                h[diff] = j
            }
            j++
        }
        i = j - 1
    }
    return res
}

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

    // 情况一，仅包括一种字符
    last := 0
    for i := 0; i < n; i++ {
        if i > 0 && s[i] == s[i-1] {
            last++
        } else {
            last = 1
        }
        if last > res {
            res = last
        }
    }

    // 情况二，包含两种字符
    res = max(res, case2Helper(s, 'a', 'b'))
    res = max(res, case2Helper(s, 'b', 'c'))
    res = max(res, case2Helper(s, 'a', 'c'))

    // 情况三，包含三种字符
    type Key struct {
        x, y int
    }
    h := make(map[Key]int)
    h[Key{n, n}] = -1

    diffAB := 0
    diffBC := 0
    for i := 0; i < n; i++ {
        c := s[i]
        switch c {
        case'a':
            diffAB--
        case'b':
            diffAB++
            diffBC++
        case'c':
            diffBC--
        }

        key := Key{diffAB + n, diffBC + n}
        if prev, exists := h[key]; exists {
            res = max(res, i-prev)
        } else {
            h[key] = i
        }
    }
    return res
}

func main() {
    s := "abbac"
    result := longestBalanced(s)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def case2_helper(s: str, x: str, y: str) -> int:
    """
    处理包含两种字符的情况
    """
    n = len(s)
    res = 0
    i = 0
    
    while i < n:
        if s[i] != x and s[i] != y:
            i += 1
            continue
        
        # 使用字典记录每个差值第一次出现的位置
        h = {}
        h[0] = i - 1
        diff = 0
        j = i
        
        while j < n and (s[j] == x or s[j] == y):
            if s[j] == x:
                diff += 1
            else:  # s[j] == y
                diff -= 1
            
            if diff in h:
                if j - h[diff] > res:
                    res = j - h[diff]
            else:
                h[diff] = j
            j += 1
        
        i = j  # 跳过已经处理过的连续段
    
    return res


def longest_balanced(s: str) -> int:
    """
    找到最长的平衡子串的长度
    平衡子串定义为：子串中所有字符的出现次数相同
    
    Args:
        s: 输入字符串，只包含字符 'a', 'b', 'c'
    
    Returns:
        最长平衡子串的长度
    """
    n = len(s)
    res = 0
    
    # 情况一：仅包含一种字符
    last = 0
    for i in range(n):
        if i > 0 and s[i] == s[i-1]:
            last += 1
        else:
            last = 1
        if last > res:
            res = last
    
    # 情况二：包含两种字符
    res = max(res, case2_helper(s, 'a', 'b'))
    res = max(res, case2_helper(s, 'b', 'c'))
    res = max(res, case2_helper(s, 'a', 'c'))
    
    # 情况三：包含三种字符
    # 使用字典记录 (diffAB, diffBC) 第一次出现的位置
    h = {}
    h[(n, n)] = -1  # 初始化，偏移量n确保索引非负
    
    diffAB = 0
    diffBC = 0
    
    for i in range(n):
        c = s[i]
        if c == 'a':
            diffAB -= 1
        elif c == 'b':
            diffAB += 1
            diffBC += 1
        else:  # c == 'c'
            diffBC -= 1
        
        key = (diffAB + n, diffBC + n)  # 加n偏移确保索引非负
        if key in h:
            res = max(res, i - h[key])
        else:
            h[key] = i
    
    return res


def main():
    s = "abbac"
    result = longest_balanced(s)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

/**
 * 处理包含两种字符的情况
 */
int case2Helper(conststring& s, char x, char y) {
    int n = s.length();
    int res = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] != x && s[i] != y) {
            continue;
        }

        unordered_map<int, int> h;
        h[0] = i - 1;
        int diff = 0;
        int j = i;

        while (j < n && (s[j] == x || s[j] == y)) {
            if (s[j] == x) {
                diff++;
            } else {
                diff--;
            }

            auto it = h.find(diff);
            if (it != h.end()) {
                if (j - it->second > res) {
                    res = j - it->second;
                }
            } else {
                h[diff] = j;
            }
            j++;
        }
        i = j - 1;
    }
    return res;
}

/**
 * 找到最长的平衡子串的长度
 * 平衡子串定义为：子串中所有字符的出现次数相同
 *
 * @param s 输入字符串，只包含字符 'a', 'b', 'c'
 * @return 最长平衡子串的长度
 */
int longestBalanced(conststring& s) {
    int n = s.length();
    int res = 0;

    // 情况一：仅包含一种字符
    int last = 0;
    for (int i = 0; i < n; i++) {
        if (i > 0 && s[i] == s[i-1]) {
            last++;
        } else {
            last = 1;
        }
        if (last > res) {
            res = last;
        }
    }

    // 情况二：包含两种字符
    res = max(res, case2Helper(s, 'a', 'b'));
    res = max(res, case2Helper(s, 'b', 'c'));
    res = max(res, case2Helper(s, 'a', 'c'));

    // 情况三：包含三种字符
    struct Key {
        int x, y;

        // 为Key结构体定义相等比较操作符，用于unordered_map
        bool operator==(const Key& other) const {
            return x == other.x && y == other.y;
        }
    };

    // 为Key结构体定义哈希函数
    struct KeyHash {
        size_t operator()(const Key& k) const {
            return hash<int>()(k.x) ^ (hash<int>()(k.y) << 1);
        }
    };

    unordered_map<Key, int, KeyHash> h;
    h[Key{n, n}] = -1;

    int diffAB = 0;
    int diffBC = 0;

    for (int i = 0; i < n; i++) {
        char c = s[i];
        if (c == 'a') {
            diffAB--;
        } elseif (c == 'b') {
            diffAB++;
            diffBC++;
        } elseif (c == 'c') {
            diffBC--;
        }

        Key key{diffAB + n, diffBC + n};
        auto it = h.find(key);
        if (it != h.end()) {
            res = max(res, i - it->second);
        } else {
            h[key] = i;
        }
    }

    return res;
}

int main() {
    string s = "abbac";
    int result = longestBalanced(s);
    cout << result << endl;

    return0;
}