咕掉/挖坑

code: 

#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#define N 1000005
#define inf 10000008
#define ll long long
using namespace std;
namespace IO {
    void setIO(string s)
    {
        string in=s+".in";
        string out=s+".out";
        freopen(in.c_str(),"r",stdin);
        // freopen(out.c_str(),"w",stdout);
    }
};
int n;
int sum[N];
char str[N];
int main()
{
    IO::setIO("input");
    int i,j,ans=0;
    scanf("%d%s",&n,str+1);
    for(i=1;i<=n;++i) G[str[i]-'a'].push_back(i);
    for(i=0;i<26;++i)
    {
        if(G[i].size())
        {
            j=1;
            for(int k=0;k<G[i].size();++k)
            {
                while(j<G[i][k])  sum[j]=sum[j-1],++j;
                ++sum[j];
            }
            for(int k=0;k<26;++k)
            {
                if(k==i||!G[k].size()) continue;
                G[k].push_back(n+1);
                int d=inf,pre=0;
                for(int p=0;p<G[k].size()-1;++p)     // 枚举每个位置
                {
                    ++pre;
                    d=min(d,sum[G[k][p]]-pre);       // 前缀最小值.
                    ans=max(ans, sum[G[k][p+1]-1]-pre-d);
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}