问题描述

原题链接🔗：4261. 孤独的照片

Farmer John 最近购入了 $N$ 头新的奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。

奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。

然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。

在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。

给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。

如果两张照片以不同位置的奶牛开始或结束，则认为它们是不同的。

输入格式
输入的第一行包含 $N$。

输入的第二行包含一个长为 $N$ 的字符串。如果队伍中的第 $i$ 头奶牛是更赛牛，则字符串的第 $i$ 个字符为 G。否则，第 $i$ 头奶牛是荷斯坦牛，该字符为 H。

输出格式
输出 Farmer John 会扔掉的孤独的照片数量。

数据范围
$3\le N\le 5\times 10^5$

输入样例：

5
GHGHG

输出样例：

3

样例解释
这个例子中的每一个长为 $3$ 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片，并会被 Farmer John 扔掉。

所有更长的子串（GHGH、HGHG 和 GHGHG）都可以被接受。

思路与代码

根据题意可知，从中任意选取一个长度大于等于 $3$ 的子串，若其中某一个字母只出现了一次，则该子串（照片）需要被扔掉。当然，不可能两个字母都只出现一次，否则子串的长度将为 $2$，与题意不符。

对于长度为 $N$ 的字符串中的某一位置，不妨设为 $G$，我们来计算它可以构成多少张孤独的照片。首先计算 $G$ 的左右两边各有多少个 $H$：

$$\underset{L个}{\underbrace{H\cdots H}}G\underset{R个}{\underbrace{H\cdots H}}$$

其中 $L\ge 0,R\ge 0$。我们来看该子串含有多少张孤独的照片，分以下三种情况考虑：

• 若 $G$ 的左右两边都至少含有一个 $H$，那么满足条件的子串共有 $L\cdot R$ 个；
• 若 $G$ 的左边至少含有一个 $H$，右边没有 $H$，那么满足条件的子串共有 $L-1$个；
• 若 $G$ 的右边至少含有一个 $H$，左边没有 $H$，那么满足条件的子串共有 $R-1$个；

将以上三种结果相加即为该位置可构成的孤独的照片的数量：$LR+L-1+R-1$。

例如，取 $L=2,R=3$，则 $HHGHHH$ 一共有 $2\cdot 3+2-1+3-1=9$ 种孤独的照片，它们分别是：

$$\begin{gathered} HGH,HGHH,HGHHH,HHGH,HHGHH,HHGHHH \\ HHG \\ GHH,GHHH \end{gathered}$$

当然，我们还需考虑特殊情形，例如当 $L=0,R>0$ 时（$L>0,R=0$ 时同理），此时 $G$ 可构成的孤独的照片的数量为 $R-1$，如果使用原来的式子计算，将会得到：$0\cdot R+0-1+R-1=R-2$，不符，因此需要做一个纠正：

$$LR+\max (L-1,0)+\max (R-1,0)$$

将所有位置可构成的孤独的照片的数量相加即可得到本题答案：

$$\sum _{i=0}^{N-1}l[i]\ast r[i]+\max (l[i]-1,0)+\max (r[i]-1,0)$$

其中 l 和 r 分别是两个数组，l[i] 代表的是第 i 个位置左边有多少个连续字母与当前位置上的字母不相同，r[i] 则代表第 i 个位置右边有多少个连续字母与当前位置上的字母不相同。

代码如下：

#include <iostream>using namespace std;const int N = 5e5 + 10;
typedef long long LL;int n;
char str[N];
int l[N], r[N];int main() {cin >> n >> str;for (int i = 0, h = 0, g = 0; i < n; i++) {if (str[i] == 'G') l[i] = h, h = 0, g++;else l[i] = g, g = 0, h++;}for (int i = n - 1, h = 0, g = 0; i >= 0; i--) {if (str[i] == 'G') r[i] = h, h = 0, g++;else r[i] = g, g = 0, h++;}LL res = 0;for (int i = 0; i < n; i++)res += (LL) l[i] * r[i] + max(l[i] - 1, 0) + max(r[i] - 1, 0);cout << res << endl;return 0;
}