把 G 记成 +1、R 记成 -1，问题就转成最长和为 0 的子数组；记录每个前缀和第一次出现的位置即可。
OJ: luogu
题目 ID: P2697
难度:普及-
标签:前缀和字符串思维
日期: 2026-06-20 10:58
题意
给定一个只由 G 和 R 组成的字符串。
要求从中截取一段最长的连续子串，使得：
G的数量- 和
R的数量
恰好相等。
输出这段子串的最大长度。
思路
先看一个最直接的小数据暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s;
int n = (int)s.size();
int ans = 0;
// 朴素枚举所有区间，统计其中 G 和 R 的数量。
for (int l = 0; l < n; l++) {
int cnt_g = 0;
int cnt_r = 0;
for (int r = l; r < n; r++) {
if (s[r] == 'G') {
cnt_g++;
} else {
cnt_r++;
}
if (cnt_g == cnt_r) {
ans = max(ans, r - l + 1);
}
}
}
cout << ans << '\n';
return 0;
}brute.cpp 枚举所有区间，统计里面 G 和 R 的个数，只要两者相等就更新答案。
这个做法很好理解，但时间复杂度是 n 可以到 10^6，显然不能通过。
第一步：把字符转成 +1 / -1
这题的核心不是字符本身，而是“两个种类数量相等”。
所以可以把：
G看成+1R看成-1
这样一段区间里：
- 如果
G和R数量相等 - 那么这段区间的总和就是
0
于是问题转成：
- 求最长的连续子数组，使它的和为
0
第二步：前缀和相同，中间这段和就是 0
设前缀和为 sum[i]，表示前 i 个字符转换后的总和。
如果存在两个位置 l < r，满足：
sum[l] = sum[r]
那么区间 (l+1 .. r) 的和就是 0。
因为：
sum[r] - sum[l] = 0
所以题目就变成：
- 对每一种前缀和值，记录它最早出现的位置
- 当它以后再次出现时，就可以用“当前下标 - 最早位置”更新答案
第三步：为什么只记第一次出现的位置
因为我们要求的是最长区间。
对某个固定的前缀和值来说：
- 最早出现的位置越靠前
- 以后再次出现时形成的区间就越长
所以只保留第一次出现的位置就够了。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
char s[MAXN];
int first_pos[MAXN * 2];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> (s + 1);
int n = (int)strlen(s + 1);
int limit = 2 * n + 2;
for (int i = 0; i <= limit; i++) {
first_pos[i] = -1;
}
int sum = 0;
int offset = n;
int ans = 0;
// 前缀和为 0 在位置 0 先出现一次。
first_pos[offset] = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == 'G') {
sum++;
} else {
sum--;
}
int idx = sum + offset;
if (first_pos[idx] == -1) {
first_pos[idx] = i;
} else {
ans = max(ans, i - first_pos[idx]);
}
}
cout << ans << '\n';
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题最关键的一步是把“G 和 R 数量相等”翻译成：
- 把两种字符映射成
+1 / -1 - 再找最长和为
0的子数组
一旦转到这个模型，标准做法就是“前缀和 + 记录第一次出现位置”。