51Nod

给出一个字符串，求该字符串的一个子串s，s包含A-Z中的全部字母，并且s是所有符合条件的子串中最短的，输出s的长度。如果给出的字符串中并不包括A-Z中的全部字母，则输出No Solution。

Input

第1行，1个字符串。字符串的长度 <= 100000。

Outpu

t输出包含A-Z的最短子串s的长度。如果没有符合条件的子串，则输出No Solution。

Sample Input

BVCABCDEFFGHIJKLMMNOPQRSTUVWXZYZZ

Sample Output

28


尺取法，判断标准是是否含有全部26个字母。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<stack>
 8 #include<deque>
 9 #include<iostream>
10 using namespace std;
11 char con[100009];
12 int main()
13 {
14     int i,p,j,k;
15     int head,tail,ans,flag,big;
16     int check[30]={0};
17     gets(con);
18     k=strlen(con);
19     big=99999999;
20     head=tail=0;
21     flag=1;
22     ans=1;
23     check[con[0]-65]++;
24     while(1)
25     {
26         if(tail>head||head>=k||tail>=k||head<0||tail<0)
27             break;
28         if(flag<26)
29         {
30             head++;
31             ans++;
32             if(check[con[head]-65]==0)
33             {
34                 flag++;
35             }
36             check[con[head]-65]++;
37         }
38         else
39         {
40             if(ans<big)
41                 big=ans;
42             ans--;
43             check[con[tail]-65]--;
44             if(check[con[tail]-65]==0)
45                 flag--;
46             tail++;
47         }
48     }
49     if(big==99999999)
50         printf("No Solution
");
51     else
52         printf("%d
",big);
53     return 0;
54 }

View Code