设f[i][j]为前i个字符中j出现的次数，则

ans=max((f[r][i]-f[l-1][i])-(f[r][j]-f[l-1][j]))=max((f[r][i]-f[r][j])-(f[l-1][i]-f[l-1][j]))，其中f[r][j]!=f[l-1][j]。

考虑枚举r，当r从r-1变化到r时，f[r][i]-f[r][j]与f[r-1][i]-f[r-1][j]只有52个值会改变。

处理这52组(i,j)，并求出min(f[l-1][i]-f[l-1][j])。

因为要满足f[r][j]!=f[l-1][j]，所以要记录f[x][i]-f[x][j]的最小值和次小值及其对应的f[x][j]，且要保证f[x][j]不相同。

若最小值对应的f[x][j]!=f[r][j]，则取最小值，否则取次小值。

时间复杂度$O(26n)$。

 

#include
     
      #define K 26int n,i,j,k,c[K],b[K][K],f0[K][K],g0[K][K],f1[K][K],g1[K][K],ans;char a[1000010];inline void max(int x){if(ans