POI #Year2011 #枚举 #贪心

枚举最后差最大的两个字符\(a,b\)，将原串中 \(a\rightarrow 1,b\rightarrow -1\)，其他标 \(0\)

原来的问题转化为强制包含 \(1,-1\) 的最大字段和问题，维护每个位置前最近的 \(-1\) ，贪心取最大的

// Author: xiaruize
const int MOD = 1000000007;
const int N = 1e6 + 10;

int n;
char s[N];
int res = 0;
int cnt[27], la[27], pos[N][27], mi[N][27];

void solve()
{
	cin >> n;
	cin >> (s + 1);
	rep(i, 1, n)
	{
		int c = s[i] - 'a';
		cnt[c]++;
		la[c] = i;
		rep(j, 0, 25)
		{
			if (j == c)
				continue;
			if (!cnt[j])
				continue;
			res = max({res,
					   cnt[c] - cnt[j] - mi[c][j] - (la[j] == pos[c][j]),
					   cnt[j] - cnt[c] - mi[j][c] - (la[c] == pos[j][c])});
		}
		rep(j, 0, 25)
		{
			if (cnt[j] - cnt[c] < mi[j][c])
			{
				mi[j][c] = cnt[j] - cnt[c];
				pos[j][c] = i;
			}
		}
	}
	cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}