孤独的照片
AcWing 4261
给定一个长度范围在 \(3 \leq n \leq n\) 的字符串，并且该字符串只会由 G 和 H 这两种字符组成。
现在有一个任务就是将该字符串按照长度 \(k\) 划分成连续的子串 \(3 \leq k \leq n\)，若 \(k\) 从 \(3\) 开始一直枚举到 \(n\)，请问划分成的连续子串中，有多少个含有孤独元素的？
孤独元素：在一个子串中，如果某个字符在该子串中只出现了 \(1\) 次，就说明该子串含有孤独元素。
输入样例
第一行输入一个整数 \(n\) 代表字符串的长度；
第二行输入一个字符串。
输出样例
输出一行，代表含有孤独元素的子串数量。
样例解释
\(k\) 的可能取值为 \(3、4、5\)，所以可以切割成的子串有：
含有孤独元素的子串是 GHG、HGH、GHG，总共有 \(3\) 个，所以输出 \(3\)。
先分析特征
若该子串含有孤独元素，那么从该孤独子串开始，向左右两边延伸，字符都会是另外一个字符，例如对于该字串 GHG 来说，孤独元素 H，围绕在 H 周围的元素都是 G，这是一个孤独元素的特征。
若有这样的字符串 GGGGGHGGGGG，我们采取的策略是从孤独元素开始 i = 6，定义左右指针 l = r = i，左指针 l 从 i 开始往左边遍历到最左边且连续的 G，那么此时能构成孤独子串的个数有 i - l + 1 >= 3 ? i - l - 1 : 0 个；右指针 r 从 i 开始往右边遍历，一直遍历到最右边且连续的 G，每遍历一次，此时能构成孤独子串的个数就有 r - i + 1 >= 3 ? i - l + 1 : r - l + 1 >= 3 ? r - l - 1 : 0。
结果就是他们两个的和。
这只是一个孤独字符的情况，多个的情况下只需按照相同的逻辑一一遍历即可。
代码参考
#include <iostream>
using namespace std;
const int N = int (1e7 + 10);
long long n, res; // 结果会爆 int
char a[N];
int main(void)
{
scanf ("%lld", &n);
scanf ("%s", a + 1);
int l, r;
for (int i = 1; i <= n; i ++)
{
l = r = i;
while (l - 1 > 0 && a[l - 1] != a[i]) l --;
if (i - l + 1 >= 3) res += i - l - 1; // 左指针遍历到最左边时，能构成孤独子串的个数
while (r + 1 <= n && a[r + 1] != a[i])
{
r ++; // 右指针每向右遍历一次，能构成孤独子串的个数
if (r - i + 1 >= 3) res += i - l + 1;
else if (r - l + 1 >= 3) res += r - l - 1;
}
}
printf ("%lld\n", res);
}