51 nod 1127最短的包含字符串（尺取法)

1127?最短的包含字符串?

?收藏

?關注

給出一個字符串，求該字符串的一個子串S，S包含A-Z中的全部字母，并且S是所有符合條件的子串中最短的，輸出S的長度。如果給出的字符串中并不包括A-Z中的全部字母，則輸出No Solution。

Input

第1行，1個字符串。字符串的長度?<=?100000。

Output

輸出包含A-Z的最短子串長度。如果沒有符合條件的子串，則輸出No?Solution。

Input示例

BVCABCDEFFGHIJKLMMNOPQRSTUVWXZYZZ

Output示例

28

#include<iostream>
#include<string>
using namespace std;
int ch[26];
bool ok()
{
? ? for(int i=0;i<26;i++)
? ? {
? ? ? ? if(ch[i]==0)return false;
? ? }
? ? return true;
}
int main()
{
? ? string s;
? ? cin>>s;
? ? int len=s.size();
? ? int ans=100005;
? ? int l=0;int r=25;
? ? for(int i=l;i<=r;i++){int t=s[i]-'A';ch[t]++;}
? ? while(l<=len-26&&r<len)
? ? {
? ? ? ? while(!ok()&&r<len-1)
? ? ? ? {
? ? ? ? ? ? ch[s[++r]-'A']++;
? ? ? ? }
? ? ? ? if(ok()){ans=min(ans,r-l+1);}
? ? ? ? ch[s[l]-'A']--;
? ? ? ? l++;
? ? }
? ? if(ans!=100005)
? ? cout<<ans<<endl;
? ? else cout<<"No Solution"<<endl;
? ? return 0;
}