题目链接

题解

考虑任意一对点的贡献，单独拿出那些点所在位置

一个设为\(1\)，一个设为\(-1\)，从头到尾扫一遍维护前缀和，以及当前最小前缀和

两者相减更新答案

需要注意的是当前最小前缀和更新的位置之后必须存在另一个字符，否则就不满足最小出现次数最少大于\(0\)的限制

由于每个位置最多拿出来\(26\)次，所以是\(O(26n)\)的

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
            
             (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
             
              #define LL long long intusing namespace std;const int maxn = 1000005,maxm = 100005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}vector
              
                pos[26];int n,ans;void work(int x,int y){ int nowx = 0,nowy = 0,minx = INF,miny = INF,mnx = 0,mny = 0; unsigned int px = 0,py = 0; while (px < pos[x].size() || py < pos[y].size()){ if (py == pos[y].size() || (px < pos[x].size() && pos[x][px] < pos[y][py])){ miny = min(miny,mny); nowx++; nowy--; px++; } else { minx = min(minx,mnx); nowy++; nowx--; py++; } mnx = min(nowx,mnx); mny = min(mny,nowy); if (minx < INF) ans = max(ans,nowx - minx); if (miny < INF) ans = max(ans,nowy - miny); }}int main(){ n = read(); int x; char c = getchar(); while (!isalpha(c)) c = getchar(); for (int i = 1; i <= n; i++){ x = c - 'a'; pos[x].push_back(i); c = getchar(); } for (int x = 0; x < 26; x++) for (int y = x + 1; y < 26; y++) work(x,y); printf("%d\n",ans); return 0;}