问题
https://vjudge.net/problem/HackerRank-beautiful-string
给一个字符串S，可以任意取走S中的两个字符从而得到另外一个字符串P，求有多少种不同的P
\(\left|S\right|\le10^6\)
题解
想到组合数
将连续的相同的字符分为1组，如字符串“aaabbbbaccca”
则可以选两组中的两个字母或一组中的两个字母
计算出连续的组数设为x
计算出长度大于等于2的组数设为y
\[ans = \left( \begin{array}{l}x\\2\end{array} \right) + y\]
时间复杂度$O(n)$
计算出长度大于等于2的组数设为y
\[ans = \left( \begin{array}{l}x\\2\end{array} \right) + y\]
时间复杂度$O(n)$
这样当然WA了
因为没有考虑是否存在两种移除（单个）字母的方法使结果相同。:(
以下考虑粗体的字母，且每种情况中xxxxx都不会造成前面情况
1.容易得aba，移除前两个字母和移除后两个字母效果相同。
2.容易得abc，（a$\ne$b，b$\ne$c，a$\ne$c），任意移除两个都不会得到相同的P
3.容易得abxxxxxc（a$\ne$b，|xxxxx|>0）和axxxxxbc（b$\ne$c，|xxxxx|>0），任意移除两个都不会得到相同的P
4.容易得axxxxxbxxxxxc，无论a，b，c相同还是不同，任意移除两个都不会得到相同的P
5.字符串A $\ne$ B，那么xxxxxAxxxxx$\ne$xxxxxBxxxxx
所以移除单个字母只会因为第一种情况造成重复
多个aba重复可以减去后面的情况，因此我们可以直接减去aba出现的次数
AC代码
#include <bits/stdc++.h>
#define REP(i,x,y) for(register int i=x; i<y; i++)
#ifdef LOCAL
#define DBG(x,...) printf(x, ##__VA_ARGS__)
#else
#define DBG(x,...) (void)(0)
#endif
using namespace std;
char S[1000007];
inline void gs(int &p) {
p=0;
while((S[p++]=getchar())>' ');
S[--p]=0;
}
int main()
{
int r;gs(r);
long long x=0,y=0;
char l=0,cn=1;
REP(i,0,r) {
if(S[i]!=l) {
x++;
if(cn>=2) y++;
cn=1;
} else {
cn++;
}
l=S[i];
}
if(cn>=2) y++,cn=1;
// DBG("%s %d %lld %lld\n", S, r, x, y);
long long ans= (x&1) ? (x-1)/2*x+y : x/2*(x-1)+y;
// long long t=0;
r--;
REP(i,1,r) {
if(S[i-1]==S[i+1] && S[i-1]!=S[i]) ans--;
}
printf("%lld\n", ans);
return 0;
}