最长平衡子串 详细题解

题目核心分析

题目定义

给定仅由 'A' 和 'B' 组成的字符串，平衡子串 指连续子串中 'A' 的数量与 'B' 的数量相等，要求找出整个字符串中最长的平衡子串长度。

数据范围与解题要求

字符串长度最大为 $2 \times 10^5$，这意味着暴力解法（枚举所有子串）会超时（暴力时间复杂度为 $O(n^2)$，对于 $2 \times 10^5$ 来说运算量达 $4 \times 10^{10}$，远超出时间限制）。因此需要设计线性时间复杂度 $O(n)$ 的高效解法。

核心问题转化

要实现线性解法，首先需要将原问题转化为更易处理的数学问题：

• 将字符 'A' 映射为整数 1，'B' 映射为整数 -1；
• 原串的平衡子串 等价于映射后和为 0 的连续子数组。

转化证明：设某连续子串中有 $k$ 个 'A' 和 $k$ 个 'B'（平衡子串定义），则映射后的和为 $k \times 1 + k \times (-1) = 0$；反之，若映射后的连续子数组和为 0，说明其中 1 和 -1 的数量相等，即原串中 'A' 和 'B' 数量相等，是平衡子串。

由此，原问题被转化为：寻找映射后数组中最长的和为 0 的连续子数组长度，这是本题的解题核心。

核心算法：前缀和 + 哈希表

1. 前缀和的定义与性质

前缀和数组定义

定义前缀和数组 sum，其中 sum[i] 表示映射后数组中前 $i$ 个元素的累加和（注意：为了方便计算，我们规定 sum[0] = 0，即前 0 个元素的和为 0，对应字符串的起始位置前）。

对于原字符串（映射后数组）的下标，我们做如下处理：将原字符串从1开始编号（原字符串第 1 个字符对应映射数组第 1 位，第 2 个字符对应第 2 位，以此类推），这样 sum[i] 能直接对应前 $i$ 个字符的和。

区间和与前缀和的关系

对于映射后数组的连续子区间 $[j+1, i]$（对应原字符串的第 $j+1$ 到第 $i$ 个字符），其区间和可以用前缀和表示为：

$$\text{区间和} = sum[i] - sum[j]$$

结合之前的问题转化，区间和为 0 等价于：

$$sum[i] - sum[j] = 0 \implies sum[i] = sum[j]$$

此时，该区间的长度为 $i - j$（原字符串中对应子串的长度）。

2. 哈希表的作用

我们的目标是找到最大的 $i - j$（$i > j$），使得 $sum[i] = sum[j]$。为了实现这一点，对于每个前缀和值，我们需要记录它第一次出现的下标 $j$：

• 若后续再次遇到相同的前缀和值 $sum[i]$，则当前 $i - j$ 是以 $i$ 为右端点的最长符合条件的子串长度；
• 若记录后续出现的下标，会导致 $i - j$ 变小，无法得到最大值。

因此，我们使用哈希表（map） 存储前缀和值 -> 其第一次出现的下标的映射，实现前缀和下标的快速查询与存储（平均时间复杂度 $O(1)$）。

3. 算法整体思路

1. 将原字符串的字符映射为 1（A）和 -1（B），并将字符串编号从 1 开始；
2. 初始化前缀和数组 sum，令 sum[0] = 0；
3. 初始化哈希表，存入初始状态 map[0] = 0（前缀和 0 第一次出现在下标 0）；
4. 遍历字符串的每个位置 $i$（从 1 到 $n$）：
   • 计算当前前缀和 sum[i] = sum[i-1] + 映射值；
   • 若哈希表中不存在 sum[i]，则将 sum[i] 和其下标 $i$ 存入哈希表（记录第一次出现的位置）；
   • 若哈希表中存在 sum[i]，则计算 $i - map[sum[i]]$，并更新最长平衡子串长度；
5. 遍历结束后，输出最长长度即为答案。

参考代码逐行解析

以下是对参考代码的逐行详细解释，包括代码逻辑、变量作用、细节处理等，同时指出代码中无关的冗余部分。

#include<bits/stdc++.h>  // 万能头文件，包含C++所有标准库（竞赛常用）
using namespace std;    // 命名空间，避免重复写std::
const int N=2e5+10;     // 定义常量N，略大于字符串最大长度2e5，防止数组越界
int t,n,a[N],ans,sum[N];// 变量声明：t（冗余，未使用）、n（字符串长度）、a[N]（字符映射数组）、ans（答案，最长平衡子串长度）、sum[N]（前缀和数组）
map<int,int> m;         // 哈希表m：key=前缀和值，value=该值第一次出现的下标
//m[i]统计前缀和为 i  第一次出现的位置，例如m[3]=10 表示前缀和3出现在位置10
string s;               // 存储输入的字符串
int main(){
    cin>>s;             // 输入仅含A、B的字符串
    n=s.size();         // 获取字符串长度n
    s="@"+s;            // 字符串前加占位符'@'，使原字符串从下标1开始（方便前缀和计算，避免下标0的处理问题）
    //1.先把字符串 转换成对应的整数数组
    for(int i=1;i<=n;i++){  // 遍历1~n（原字符串的所有字符）
        if(s[i]=='A') a[i]=1;   // A映射为1
        else a[i]=-1;           // B映射为-1
    }
    m[0]=0;             // 初始化哈希表：前缀和0第一次出现在下标0
    //AAABBB 测试用例注释，可忽略
    //2.遍历每一个位置  计算以i作为右端点 的所有区间里面 最长的符合条件的
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];   // 计算前i个字符的前缀和：当前和 = 前i-1个和 + 第i个字符的映射值
        //当前 前i个位置的总和 是 sum[i]
        if(m.count(sum[i])==0){// 哈希表中不存在sum[i]，说明是第一次出现
            m[sum[i]]=i;       // 记录sum[i]第一次出现的下标i
        }else{                 // 哈希表中存在sum[i]，说明存在j< i使得sum[j]=sum[i]
            ans=max(ans,i-m[sum[i]]); // 更新答案：取当前ans和i-j的最大值
        }
    }
    cout<<ans;          // 输出最长平衡子串长度
    return 0;           // 程序结束
}

代码关键细节说明

1. 字符串下标处理：s="@"+s 是竞赛中常用的技巧，将原字符串从下标1开始，避免前缀和 sum[0] 与字符串下标0冲突，简化逻辑；
2. 冗余变量：变量 t 未被使用，是代码模板的残留，可直接删除，不影响程序运行；
3. 数组优化：实际上不需要开 a[N] 和 sum[N] 两个数组，可通过变量实时计算节省空间（见下文优化代码）；
4. 哈希表选择：map 的查询/插入时间复杂度为 $O(\log n)$，对于 $2e5$ 来说完全够用；若想进一步优化，可使用 unordered_map（平均 $O(1)$ 复杂度），效果更好。

代码空间优化版（更高效）

去掉不必要的数组，用变量实时计算映射值和前缀和，空间复杂度从 $O(n)$ 优化为 $O(1)$（哈希表空间除外）：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,ans,cur_sum; // cur_sum：实时计算的前缀和，替代sum数组
unordered_map<int,int> m; // 更高效的哈希表
string s;
int main(){
    cin>>s;
    n=s.size();
    m[0]=0;
    cur_sum=0;
    for(int i=1;i<=n;i++){
        // 实时计算映射值，替代a数组
        cur_sum += (s[i-1]=='A' ? 1 : -1); // 原字符串s是0开始，对应i从1开始
        if(m.find(cur_sum)==m.end()){
            m[cur_sum]=i;
        }else{
            ans=max(ans,i-m[cur_sum]);
        }
    }
    cout<<ans;
    return 0;
}

样例全程模拟

以样例输入 AABBAA 为例，全程模拟代码执行过程，直观理解算法逻辑。

样例输入预处理

• 输入字符串 s = "AABBAA"，长度 $n=6$；
• 执行 s="@"+s 后，$s = "@AABBAA"$，下标1~6分别为：A A B B A A；
• 映射数组 a[1~6] = [1,1,-1,-1,1,1]；
• 初始化：m[0]=0，ans=0，sum[0]=0。

遍历过程（i从1到6）

i	s[i]	a[i]	sum[i] = sum[i-1]+a[i]	m中是否存在sum[i]	哈希表m的变化	i - m[sum[i]]	ans（最大值）
1	A	1	sum[0]+1 = 1	否（m无1）	m[1] = 1	-	0
2			sum[1]+1 = 2	否（m无2）	m[2] = 2
3	B	-1	sum[2]-1 = 1	是（m[1]=1）	无	3-1=2	max(0,2)=2
4			sum[3]-1 = 0	是（m[0]=0）		4-0=4	max(2,4)=4
5	A	1	sum[4]+1 = 1	是（m[1]=1）		5-1=4	max(4,4)=4
6			sum[5]+1 = 2	是（m[2]=2）		6-2=4

模拟结果

遍历结束后，ans=4，与样例输出一致，验证了算法的正确性。

边界情况测试

为了确保算法的鲁棒性，测试以下典型边界情况：

情况1：无平衡子串（全A/全B）

输入：AAAAA，映射后为 [1,1,1,1,1]，前缀和依次为 1,2,3,4,5，哈希表中无重复值，ans=0，输出0。

情况2：整个字符串都是平衡子串

输入：ABAB，映射后为 [1,-1,1,-1]，前缀和依次为 1,0,1,0：

• i=2时，sum=0，2-0=2，ans=2；
• i=4时，sum=0，4-0=4，ans=4； 输出4，正确。

情况3：单字符

输入：A，长度1，无平衡子串，输出0。

情况4：两字符平衡

输入：AB，前缀和依次为1,0，2-0=2，输出2，正确。

时间与空间复杂度分析

时间复杂度

• 遍历字符串两次（一次映射，一次计算前缀和），时间为 $O(n)$；
• 哈希表的 count/find/insert 操作，map 为 $O(\log n)$，unordered_map 平均为 $O(1)$；
• 整体时间复杂度：使用 map 为 $O(n \log n)$，使用 unordered_map 为 $O(n)$，均能满足 $2e5$ 的数据范围。

空间复杂度

• 若使用原代码的数组 a[N] 和 sum[N]，空间为 $O(n)$；
• 若使用优化版代码（无数组），哈希表的空间为 $O(n)$（最坏情况：前缀和全不重复，如全A，哈希表存储n个值）；
• 整体空间复杂度为 $O(n)$，符合题目要求。

解题关键点总结

1. 问题转化是核心：将A/B映射为1/-1，把“平衡子串”转化为“和为0的连续子数组”，是线性解法的基础；
2. 前缀和的性质：利用 sum[i] = sum[j] 等价于区间 $[j+1,i]$ 和为0，将问题转化为寻找相同前缀和的最大下标差；
3. 哈希表的关键作用：记录前缀和第一次出现的下标，保证能得到最大的子串长度；
4. 初始化的重要性：哈希表必须提前存入 m[0]=0，处理从第一个字符开始的平衡子串（如样例中i=4时，sum=0，对应前4个字符的平衡子串）；
5. 下标处理技巧：将字符串从1开始编号，简化前缀和与字符串下标的对应关系，避免逻辑混乱。