2026-03-07：最长的平衡子串Ⅰ。用go语言，给定一个只含小写字母的字符串 s。我们把任意连续且非空的字符区间称为一个片段；当该片段内每

福大大架构师每日一题

发布于 2026-03-09 14:10:43

460

2026-03-07：最长的平衡子串Ⅰ。用go语言，给定一个只含小写字母的字符串 s。我们把任意连续且非空的字符区间称为一个片段；当该片段内每一种不同字母出现的频次都相同，就称它为“均衡片段”。请找出 s 中最长的均衡片段，并返回它的长度。

1 <= s.length <= 1000。

s 仅由小写英文字母组成。

输入： s = "abbac"。

输出： 4。

解释：

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

题目来自力扣3713。

一、解题过程分步解析

整个算法采用暴力枚举所有子串 + 验证是否为均衡片段的思路，具体步骤如下：

步骤1：初始化核心变量

• 首先获取字符串s的长度n，用于后续遍历边界控制；
• 初始化结果变量res为0，用于记录找到的最长均衡片段的长度（初始为0表示未找到任何有效片段）。

步骤2：枚举所有可能的子串起点

外层循环遍历字符串的每一个位置i（从0到n-1），将i作为子串的起始索引：

• 对于每个起点i，首先创建一个长度为26的数组cnt（对应26个小写字母），初始值全为0，用于统计当前子串中每个字母的出现次数；
• 这个cnt数组会在每次更换起点i时重新初始化，保证统计的是“以i为起点的子串”的字母频次。

步骤3：枚举所有可能的子串终点，验证均衡性

内层循环遍历从起点i到字符串末尾的每一个位置j（从i到n-1），将j作为子串的结束索引：

1. 统计当前字母频次：
- • 取出当前位置j的字符s[j]，转换为0-25的索引（c = s[j] - 'a'，比如'a'对应0，'b'对应1）；
- • 将cnt[c]加1，记录该字母在i~j子串中又出现了一次。
2. 验证当前子串是否为均衡片段：
- • 初始化标记变量flag为true（假设当前子串是均衡的）；
- • 遍历cnt数组的所有26个元素（对应所有小写字母）：
  - • 对于每个元素x（某字母的出现次数），如果x > 0（说明该字母出现在当前子串中），且x != cnt[c]（当前新增字母的出现次数），则说明子串中存在出现次数不同的字母，将flag设为false并跳出遍历；
  - • （核心逻辑：均衡片段要求“所有出现过的字母频次相同”，因此只需验证所有非零频次是否等于当前最后一个新增字母的频次即可）。
3. 更新最长片段长度：
- • 如果flag仍为true（当前i~j子串是均衡片段），且子串长度j-i+1大于当前记录的res，则更新res为j-i+1。

步骤4：以输入用例`s = "abbac"`为例，模拟执行过程

输入字符串索引：0:a，1:b，2:b，3:a，4:c

• 当i=0（起点为a）：
- • j=0（子串"a"）：cnt[0]=1，其他为0。遍历cnt，只有cnt[0]=1非零，满足“所有非零频次相同”，res更新为1；
- • j=1（子串"ab"）：cnt[0]=1，cnt[1]=1。所有非零频次都是1，满足条件，res更新为2；
- • j=2（子串"abb"）：cnt[0]=1，cnt[1]=2。cnt[0]≠cnt[1]，不满足；
- • j=3（子串"abba"）：cnt[0]=2，cnt[1]=2。所有非零频次都是2，满足条件，res更新为4；
- • j=4（子串"abbac"）：cnt[0]=2，cnt[1]=2，cnt[2]=1。cnt[2]≠2，不满足；
• 当i=1（起点为b）：
- • 后续子串如"b"（长度1）、"bb"（长度2）、"bba"（频次1、2、1，不满足）、"bbac"（频次1、2、1、1，不满足），最长有效长度为2，小于当前res=4；
• 当i=2、i=3、i=4时：
- • 后续子串的最长有效长度均小于4；
• 最终res=4，与题目输出一致。

步骤5：返回最终结果

遍历完所有起点和终点后，返回res即为最长均衡片段的长度。

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

1. 时间复杂度

• 外层循环（枚举起点）：遍历n次（n为字符串长度）；
• 内层循环（枚举终点）：对于每个起点i，最多遍历n-i次，整体为O(n²)；
• 内层验证逻辑（遍历cnt数组）：每次验证需要遍历26个元素（固定次数），可视为O(1)；
• 总时间复杂度：O(n² × 26) = O(n²)（26是常数，可忽略）。

2. 额外空间复杂度

• 主要空间消耗是每个起点i对应的cnt数组：长度固定为26，占用O(26) = O(1)的空间；
• 其他变量（res、flag、循环变量i/j/c等）：占用O(1)的固定空间；
• 总额外空间复杂度：O(1)（无论字符串多长，空间消耗都是固定的）。

总结

1. 核心流程：暴力枚举所有可能的子串（通过双层循环确定起点和终点），用长度为26的数组统计子串字母频次，验证所有出现过的字母频次是否相同，最终记录最长符合条件的子串长度；
2. 关键操作：通过固定长度的数组统计频次，避免了哈希表的额外开销，验证时只需检查所有非零频次是否等于当前新增字母的频次；
3. 复杂度：时间复杂度为O(n²)（n为字符串长度），额外空间复杂度为O(1)（仅使用固定长度的数组和少量变量）。

Go完整代码如下：

package main

import (
    "fmt"
)

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

    for i := 0; i < n; i++ {
        cnt := make([]int, 26)

        for j := i; j < n; j++ {
            c := s[j] - 'a'
            cnt[c]++
            flag := true

            for _, x := range cnt {
                if x > 0 && x != cnt[c] {
                    flag = false
                    break
                }
            }

            if flag && (j-i+1) > res {
                res = j - i + 1
            }
        }
    }
    return res
}

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

Python完整代码如下：

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

def longest_balanced(s: str) -> int:
    """
    找到最长的平衡子串的长度
    平衡子串定义为：子串中出现的所有字符的出现次数相同
    
    Args:
        s: 输入字符串
    
    Returns:
        最长平衡子串的长度
    """
    n = len(s)
    res = 0
    
    # 遍历所有可能的子串起始位置
    for i in range(n):
        # 统计当前子串中每个字符出现的次数
        cnt = [0] * 26
        
        # 扩展子串的结束位置
        for j in range(i, n):
            c = ord(s[j]) - ord('a')  # 将字符转换为索引（0-25）
            cnt[c] += 1
            
            # 检查当前子串是否平衡
            flag = True
            for x in cnt:
                if x > 0 and x != cnt[c]:
                    flag = False
                    break
            
            # 如果是平衡子串且长度更长，更新结果
            if flag and (j - i + 1) > res:
                res = j - i + 1
    
    return res


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


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    // 遍历所有可能的子串起始位置
    for (int i = 0; i < n; i++) {
        // 统计当前子串中每个字符出现的次数
        vector<int> cnt(26, 0);

        // 扩展子串的结束位置
        for (int j = i; j < n; j++) {
            int c = s[j] - 'a';  // 将字符转换为索引（0-25）
            cnt[c]++;

            // 检查当前子串是否平衡
            bool flag = true;
            for (int x : cnt) {
                if (x > 0 && x != cnt[c]) {
                    flag = false;
                    break;
                }
            }

            // 如果是平衡子串且长度更长，更新结果
            if (flag && (j - i + 1) > res) {
                res = j - i + 1;
            }
        }
    }

    return res;
}

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

    return0;
}