题目描述

Description

A word consisting of lower-case letters of the English alphabet ('a'-'z') is given. We would like to choose a non-empty contiguous (i.e. one-piece) fragment of the word so as to maximise the difference in the number of occurrences of the most and the least frequent letter in the fragment. We are assuming that the least frequent letter has to occur at least once in the resulting fragment. In particular, should the fragment contain occurrences of only one letter, then the most and the least frequent letter in it coincide.

已知一个长度为n的由小写字母组成的字符串，求其中连续的一段，满足该段中出现最多的字母出现的个数减去该段中出现最少的字母出现的个数最大。求这个个数。

Input

The first line of the standard input holds one integer (1<=N<=1000000)() that denotes the length of the word. The second line holds a word consisting of lower-case letters of the English alphabet.
第一行，n
第二行，该字符串
1<=n<=1000000

Output

The first and only line of the standard output is to hold a single integer, equal to the maximum difference in the number of occurrences of the most and the least frequent letter that is attained in some non-empty contiguous fragment of the input word.
一行，表示结果

Sample Input

10
aabbaaabab

Sample Output

3

题目分析

用奇怪的贪心骗掉了
设表示1~i中j出现的个数 假设枚举到i，那我们需要使最大
相当于最大
前一部分我们知道 后一部分我们可以存储下来
但是我们这么算是拿出了(j+1~i)的区间，需要满足这段区间内有x,y;
有x是肯定的了(因为你枚举到第i位上就是i) 那么我们要满足这段区间有y
那就记录一下最小差时x y的个数都是什么 以此来判定是否区间内有y
但是有bug 当选出的这段区间内真的没有y时 这么做就不能更新了 所以还要保存一个次小差值用来更新
但是这么做好麻烦 注意把出bug的地方反转，就会避免这种情况,并且答案不变
那我们把原串反转 再拍一遍就好了
时间复杂度
感觉这么做还是会有bug，求hack~~~

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,num[26][26],sum1[26][26],sum2[26][26],sum[26],ans;
char s[1000100];
void work()
{
    for(int x,i=1;i<=n;i++)
    {
        x=s[i]-'a',sum[s[i]-'a']++;
        for(int j=0;j<26;j++)
            if(j!=x&&sum[j]) 
            {
                if(sum[j]!=sum2[x][j]) ans=max(ans,sum[x]-sum[j]-num[x][j]);
                if(sum[j]!=sum1[j][x]) ans=max(ans,sum[j]-sum[x]-num[j][x]);
            }
        for(int j=0;j<26;j++)
        {
            if(sum[j]-sum[x]<num[j][x]) num[j][x]=sum[j]-sum[x],sum1[j][x]=sum[j],sum2[j][x]=sum[x];
            if(sum[x]-sum[j]<num[x][j]) num[x][j]=sum[x]-sum[j],sum1[x][j]=sum[x],sum2[x][j]=sum[j];
        }
    }
}
void init()
{
    memset(sum,0,sizeof sum);
    memset(sum1,0,sizeof sum1);
    memset(sum2,0,sizeof sum2);
    memset(num,0,sizeof num);
}
int main()
{   
    scanf("%d%s",&n,s+1);
    work(),init();
    for(int i=1;i<=n/2;i++) swap(s[i],s[n-i+1]);
    work();
    printf("%d",ans);
    return 0;
}