登录
枚举 & 前缀和 & 哈希表
解法：枚举 & 前缀和 & 哈希表
先考虑简单一点的问题：如果只有字母 a 和 b 怎么做？
这是一个经典的用前缀和维护的题目。假设平衡子串的下标范围是 $[l, r]$，设 $a_i$ 表示字母 a 在长度为 $i$ 的前缀里的出现次数，$b_i$ 表示字母 b 在长度为 $i$ 的前缀里的出现次数，则
$$
a_r - a_{l - 1} = b_r - b_{l - 1}
$$
移项得
$$
a_r - b_r = a_{l - 1} - b_{l - 1}
$$
因此，类似于 leetcode 974. 和可被 K 整除的子数组，我们枚举子串的右端点 $r$，并找到 $\Delta = (a_i - b_i)$ 的值与 $r$ 相同的最小下标 $l$，则以 $r$ 为右端点的平衡子串的最大长度就是 $(r - l)$。我们可以把 $\Delta$ 的值放入哈希表，并对每个 $\Delta$ 维护最小的下标。
回到当前问题，现在增加了一个字母 c，我们能不能用类似的方法做呢？设 $c_i$ 表示字母 c 在长度为 $i$ 的前缀里的出现次数，我们继续分析一下平衡子串的条件
$$
\begin{matrix}
a_r - a_{l - 1} = b_r - b_{l - 1} \
b_r - b_{l - 1} = c_r - c_{l - 1} \
\end{matrix}
$$
移项得
$$
\begin{matrix}
a_r - b_r = a_{l - 1} - b_{l - 1} \
b_r - c_r = b_{l - 1} - c_{l - 1} \
\end{matrix}
$$
因此，我们仍然可以用相同的做法求出平衡子串的最大长度，只不过哈希表的 key 不是一个整数 $(a_i - b_i)$，而是一个数对 $(a_i - b_i, b_i - c_i)$。
复杂度 $\mathcal{O}(n)$（认为字符集大小是常数）。
其实，这个做法也可以推广到任意字符集，复杂度 $\mathcal{O}(n|\Sigma| \times 2^{|\Sigma|})$，其中 $|\Sigma|$ 是字符集大小。有兴趣的读者可以试着做一下本题强化版 CF GYM100584D - Balanced strings，链接就不附了，怕扣子又把我帖子搞没了。
参考代码（c++）
class Solution {
public:
int longestBalanced(string s) {
int n = s.size(), ans = 0;
// 子串只包含一个字母的情况
auto calc1 = [&]() {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || s[i] == s[i - 1]) cnt++;
else cnt = 1;
ans = max(ans, cnt);
}
};
// 子串只包含两个字母的情况
auto calc2 = [&](char a, char b) {
unordered_map<int, int> mp;
mp[0] = -1;
// x 表示 a_i - b_i 的值
int x = 0;
for(int i = 0; i < n; i++) {
if (s[i] == a) x++;
else if (s[i] == b) x--;
else {
// 遇到不在子串里的字符，截断
mp.clear();
x = 0;
}
if (mp.count(x)) ans = max(ans, i - mp[x]);
else mp[x] = i;
}
};
// 子串包含三个字母的情况
auto calc3 = [&]() {
unordered_map<long long, int> mp;
mp[0] = -1;
// x 表示 a_i - b_i 的值
// y 表示 b_i - c_i 的值
int x = 0, y = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'a') x++;
else if (s[i] == 'b') x--, y++;
else y--;
// c++ 的 unordered_map 不支持用 pair 作为 key
// 所以只能把数对映射成一个整数
// 当然也可以直接用 map，用 pair 作为 key
// 只是复杂度会乘上一个 log
long long key = 10LL * x * n + y;
if (mp.count(key)) ans = max(ans, i - mp[key]);
else mp[key] = i;
}
};
calc1();
calc2('a', 'b');
calc2('a', 'c');
calc2('b', 'c');
calc3();
return ans;
}
};
不会做怎么办
读者首先需要掌握用前缀和 + 哈希表的方式，求特定子数组数量或最大长度的方法。读者可以学习 灵神题单 - 常用数据结构 的“前缀和与哈希表”一节。
如果读者掌握了这一技巧，那么至少可以解答只包含 a 和 b 的情况。若此时仍然不会做本题，需要加强从特殊到一般的拓展能力。一般来说可以先考虑一个简化的问题怎么做（例如图上问题先想一下树上怎么做，树上问题先想一下链上怎么做，二维矩阵问题先想一下一维序列怎么做），这只能在大量的练习中慢慢习得。
