[文章目录]
Description
已知一个长度为n的由小写字母组成的字符串，求其中连续的一段，满足该段中出现最多的字母出现的个数减去该段中出现最少的字母出现的个数最大。求这个个数。n<=10^6
维护每种字符出现次数的前缀和，那么答案即为s[r]-s[l]-s'[r]+s'[l]=(s[r]-s'[r])+(s'[l]-s[l])
维护每两个字符的前缀和之差的最大值，由于每次只会有一个前缀和改变，所以修改的复杂度为O(26)。另外由于题目中所选的字符必须是出现了的，所以需要满足：s'[l]!=s'[now]，多维护一个数组表示s[l]==s[now]的前缀之差最大值即可。时间复杂度O(26n)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define R register
int ans,use[30][30],now[30][30],s[30];
//use[i][j]-> max(s[i]-s[j])&&s[i]!=s[now] now[i][j]->max(s[i]-s[j])&&s[i]=s[now];
int Max(int x,int y){return x>y ? x:y;}
inline char nc()
{
char ch=getchar();
while(ch<'a'||ch>'z') ch=getchar();
return ch;
}
int main()
{
R int n,j,x;
scanf("%d",&n);
memset(use,0xef,sizeof use);
while(n--)
{
x=nc()-'a'; s[x]++;
for(j=0;j!=26;++j) if(x!=j)
{
use[x][j]=Max(use[x][j],now[x][j]);
now[x][j]=s[x]-s[j];
ans=Max(ans,Max(now[x][j]+use[j][x],s[j]-s[x]+use[x][j]));
}
}
printf("%d",ans);
return 0;
}