題目描述?

小N現(xiàn)在有一個字符串S。他把這這個字符串的所有子串都挑了出來。一個S的子串T是合法的，當(dāng)且僅當(dāng)T中包含了所有的小寫字母。小N希望知道所有的合法的S的子串中，長度最短是多少。

輸入描述:

一行一個字符串S。只包含小寫字母。S的長度不超過106.

輸出描述:

一行一個數(shù)字，代表最短長度。數(shù)據(jù)保證存在一個合法的S的子串。 示例1

輸入

復(fù)制 ykjygvedtysvyymzfizzwkjamefxjnrnphqwnfhrnbhwjhqcgqnplodeestu

輸出

復(fù)制 49

1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstdlib> 5 #include <cstring> 6 #include <string> 7 #include <deque> 8 #include <set> 9 #include <queue> 10 using namespace std; 11 #define ll long long 12 #define N 1000009 13 #define gep(i,a,b) for(int i=a;i<=b;i++) 14 #define gepp(i,a,b) for(int i=a;i>=b;i--) 15 #define gep1(i,a,b) for(ll i=a;i<=b;i++) 16 #define gepp1(i,a,b) for(ll i=a;i>=b;i--) 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define P pair<int,int>u+ 19 char s[N]; 20 int loc[30]; 21 int main() 22 { 23 scanf("%s",s); 24 int l=0; 25 int len=strlen(s); 26 int ans=len+1; 27 mem(loc,-1); 28 int cnt=0; 29 //只要[l,i]區(qū)間里含有26個字母即可 30 gep(i,0,len-1) 31 { 32 if(loc[s[i]-'a']==-1) 33 { 34 cnt++; 35 } 36 loc[s[i]-'a']=i;//該字母最大的坐標(biāo) 37 while(l<loc[s[l]-'a']) l++;//后面有了，那么前面的就可以不用了，l++。減小去區(qū)間長度 38 if(cnt==26) 39 { 40 ans=min(ans,i-l+1); 41 } 42 } 43 printf("%d\n",ans); 44 return 0; 45 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/tingtin/p/9568631.html

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的Wannafly挑战赛23 A字符串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。