二分做法
一共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; }