Description：

给一个只包含 $26$ 个小写英文字母的字符串，从中找出一段使得这一段中出现最多的字母出现的次数与出现最少的字母出现的次数的差值最大。

$1\le n \le 1000000$

Solution：

做法太神仙。

记一个 $mat[i][j]$ 表示以 $i$ 为区间出现最多的字母， $j$ 为最少的的最大差值，那么到了这一位，设这位的字母是 $ch$ ，那么枚举 $26$ 个字母，设为 $j$ ，那么 $++mat[ch][j]$ ， $--mat[j][ch]$ ，注意这时不能用 $mat[ch][j]$ 更新答案因为不一定最少出现的出现过，但 $mat[j][ch]$ 可以被看成出现过，因为就算没有出现过也不会用他更新答案，所以把这个设成合法，如果 $mat[j][ch]<-1$ ，那么我们可以把一个前缀删掉使得它变成 $-1$ ，而这时他有一个前缀字符是 $j$ ，我们把这个状态打上标记 $(pre)$ ，每次如果 $ch$ 是区间最少出现过的字符，那么就减去 $pre$ ，也就是处理 $abbba$ 的情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

char c[MAXN];

int mat[26][26];

bool occur[26][26];

bool pre[26][26];

int main()

{

	while(scanf("%d",&n) != EOF)

	{

		memset(mat,0,sizeof(mat));

		memset(pre,false,sizeof(pre));

		memset(occur,false,sizeof(occur));

		scanf("%s",c + 1);

		int ans = 0;

		for(int i = 1;i <= n;++i)

		{

			int ch = c[i] - 'a';

			for(int j = 0;j < 26;++j)

			{

				if(j == ch)continue;

				++mat[ch][j];

				if(mat[ch][j] > ans && occur[ch][j])ans = mat[ch][j];

				--mat[j][ch];occur[j][ch] = true;

				if(pre[j][ch])++mat[j][ch],pre[j][ch] = false;

				if(mat[j][ch] > ans)ans = mat[j][ch];

				if(mat[j][ch] < -1)mat[j][ch] = -1;

				if(mat[j][ch] == -1)pre[j][ch] = true;

			}

		}

		cout << ans << endl;

	}

	return 0;

}