思路：
首先，比较容易确定的是答案为长度为1的字符串跟长度为2的字符串。
其次，我的思路是用一个前缀和a [ i ] [ j ]维护前i个字母中，字母j的出现次数。然后再倒着扫一遍，维护b [ i ] [ j ]表示后i个字母中，字母j的出现次数，更新b的时候更新答案。
这样有一组hack样例，
比如a a a a a，答案应该为10，说明上面的过程无法累加相同的字符，对于这个样例，每次都对a a 的个数进行了计算，却没有累加。
正确的是用a [ i ] [ j ]表示字母i与字母j的组合的个数，c [ i ]表示字母i的出现次数，从头扫一遍，每次都维护两个数组。
a[j][t]+=c[j];
表示计算j t的个数，其中c [ j ]记录的是当前枚举到i时，前面的j出现的次数。
正确代码
const int maxn=1e5+7,maxm=210000; ll a[26][maxn],b[maxn][26],c[26]; char s[maxn]; int main(){ cin>>s+1; int n=strlen(s+1); ll res=0; for(int i=1;i<=n;i++){ int t=s[i]-'a'; for(int j=0;j<26;j++) a[j][t]+=c[j]; c[t]++; } sort(c,c+26); res=c[25]; rep(i,0,25) rep(j,0,25) res=max(res,a[i][j]); cout<<res<<endl; return 0; }
错误代码
// Problem: 隐藏字符串 // Contest: AcWing // URL: https://www.acwing.com/problem/content/3792/ // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } inline void out(ll x){ if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) out(x / 10); putchar(x % 10 + '0'); } inline void write(ll x){ if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b) { ll res = 1; while(b) { if(b & 1)res = res * a ; a = a * a ; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; const int maxn=1e5+7,maxm=210000; ll a[maxn][26],b[maxn][26],c[26]; char s[maxn]; int main(){ cin>>s+1; int n=strlen(s+1); ll res=0; rep(i,1,n){ for(int j=0;j<26;j++){ if(s[i]-'a'==j) a[i][j]=a[i-1][j]+1; else a[i][j]=a[i-1][j]; } c[s[i]-'a']++; res=max(res,c[s[i]-'a']); } for(int i=n;i;i--){ for(int j=0;j<26;j++) if(s[i]-'a'==j) b[i][j]=b[i+1][j]+1; else b[i][j]=b[i+1][j]; for(int j=0;j<26;j++) if(s[i]-'a'!=j) res=max(res,b[i][s[i]-'a']*a[i-1][j]); else res=max(res,b[i][s[i]-'a']+a[i-1][j]); } cout<<res<<endl; return 0; }
