二分做法

一共26个字符,对于每个字符将他们的位置都记录下来
然后从前往后遍历字符串,对于每个字符,二分寻找其他25个字符大于该位置且离该位置最远的位置是多少,最远的位置减当前位置即是一次满足条件的子串的长度,最后找出最小的长度即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

char s[1000005];
int pos[30][1000006];
int c[30],op;
int main()
{
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;i++)
    {
        op=s[i]-'a';
        pos[op][c[op]++]=i;
    }
    int ans=999999999,flag=1,w,dis;
    for(int i=0;i<n;i++)
    {
        op=s[i]-'a';
        dis=-1;
        for(int j=0;j<26;j++)
        {
            if(j==op){continue;}
            w=upper_bound(pos[j],pos[j]+c[j],i)-pos[j];
            if(w==c[j]){flag=0;break;}
            dis=max(pos[j][w],dis);
        }
        if(flag==0){break;}
        ans=min(ans,dis-i+1);
    }
    printf("%d\n",ans);
    return 0;
}