1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| #include<stdio.h> #include<set>
#include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<string.h> #define mem(ss) memset(ss,0,sizeof(ss)) #define rep(d, s, t) for(int d=s;d<=t;d++) #define rev(d, s, t) for(int d=s;d>=t;d--) typedef long long ll; typedef long double ld; typedef double db; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
char s[100020]; int len,ans; int zm[30],cnt; bool check(int x){ memset(zm,0,sizeof(zm)); cnt=0; for(int i=0;i<x;i++){ zm[s[i]-'A']++; if(zm[s[i]-'A']==1) cnt++; } if(cnt==26) return true; for(int i=x;i<len;i++){ zm[s[i]-'A']++; if(zm[s[i]-'A']==1) cnt++; zm[s[i-x]-'A']--; if(zm[s[i-x]-'A']==0) cnt--; if(cnt==26) return true; } return false; } int main() { scanf("%s",s); len=strlen(s); int l=0,r=len,mid; while(l<=r){
mid=(l+r)/2; if(check(mid)){ r=mid-1; ans=mid; } else{ l=mid+1; } } if(ans) printf("%d\n",ans); else printf("No Solution\n"); return 0; }
|