今天联考T2，蒟蒻抢了最优解来水篇题解 其实是蒟蒻的第一篇题解

前置知识: 最大子段和。

由于字符集很小，只有 $26$ 所以我们可以钦定最多出现次数的字符 $a$ 与最少的字符 $b$（注意 $a,b$ 都必须是字符串中出现过的），将所有 $a$ 赋值为 $1$，所有 $b$ 赋值为 $-1$，其余字符赋值为 $0$，求强制至少选一个 $-1$ 的最大字段和。

我们用 $f[a][b]$ 表示以钦定 $a$ 为最多出现次数的字符，$b$ 为最少出现次数的字符的最大子段和。容易发现 $f[a][b]$ 的转移只与上一次的 $f[a][b]$ 和下一次的 $a,b$ 出现的位置有关，于是可以直接滚动数组，从左往右枚举字符 $s[i]$，并处理 $a=s[i]$ 与 $b=s[i]$ 的情况，剩下的一维则枚举。

记 $a=s[i]$。

$f[a][b]$ 更新为 $f[a][b]+1$ 表示一定会选当前这个 $a$。

$f[b][a]$ 更新为 $\max(0, f[b][a] - 1)$。

考虑如何强制至少选一个 $-1$：

我们用 $h[a][b]$ 表示当前选/没选至少一个 $-1$ 。则统计答案时记为 $f[a][b]- (\neg h[a][b])$。

$h[b][a]$ 随 $f[b][a]$ 转移，当 $f[b][a]\ge1$ 时有 $h[b][a]=1$。

代码很好写：

#include <bits/stdc++.h>
#define a s[i]
using namespace std;
int f[26][26], n, A, i, v[26];
bool h[26][26];char s[1000001];
vector<int> e;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s;
    for (i = 0; i < n; ++i)
        if (!v[a -= 'a']) {
            v[a] = 1;
            e.push_back(a);//记录出现过的字符集 
        }
    for (i = 0; i < n; ++i)
        for (int b : e)
            if (b ^ a) {
                ++f[a][b];  
                A = max(A, f[a][b] - !h[a][b]);//记录答案，如果没有选-1要减去1 
                h[b][a] = f[b][a];//h为bool类型 表示h[b][a]=[f[b][a]>=1],若上一次的f[b][a]不为0表示可选这个-1 
                f[b][a] = max(0, f[b][a] - 1);
            }
    cout << A;
    return 0;
}

时间复杂度 $O(n)$ 常数极小，跑了124ms。