# Wannafly challenge 23A - string

Source: niuke.com
Title Description
Small N now has a string s. He picked out all the substrings of the string. The substring T of an S is legal if and only if it contains all lowercase letters. Small N wants to know the shortest length of all legal s substrings.
Enter a description:
One string per line, S. Contains only lowercase letters. The length of s does not exceed 106
Output Description:
One number per line, representing the shortest length. Data guarantees the existence of a valid S substring.
Example 1
input
copy
ykjygvedtysvyymzfizzwkjamefxjnrnphqwnfhrnbhwjhqcgqnplodeestu
output
copy
49

Cheating signed in a question ..
In the game, I asked the big guy to learn the problem of minimum covering substring
Code:

```#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=105;
//Minimum length of substring satisfying the condition
char s[N];
char t[N];
//The number of times each letter of the target string and the original string appears. Here, 26 lowercase letters are considered
int sHash;
int tHash;
int main(void){
int tlen=strlen(t);
int slen=strlen(s);
//Preprocessing hash array of target string
for(int i=0;i<tlen;i++){
tHash[t[i]-'a']++;
}
//Temporary string start
int ss=0;
int found=0;
//Start and end of substring
int start=-1;
int end=slen;
int minLen=slen;
for(int i=0;i<slen;i++){
sHash[s[i]-'a']++;
//The number of occurrences after the addition is not greater than the number of occurrences of the character in the target string, i.e. a matching character is found
//For example, if t is aab, if s is a a a, and the first two A's are found + +, the third a will not
if(sHash[s[i]-'a']<=tHash[s[i]-'a']){
found++;
}
//Find a substring that meets the requirements
if(found==tlen){
//Skip the useless beginning of the substring (useless means that the number of occurrences of the character is no greater than that of the character in the target string
//Therefore, deletion will not affect)
while(ss<i && sHash[s[ss]-'a']>tHash[s[ss]-'a']){
sHash[s[ss]-'a']--;
//Starting point plus 1
ss++;
}
if(i-ss<minLen){
minLen=i-ss+1;
start=ss;
end=i;
}
//Delete the beginning, and remember to subtract 1 from the number of matching characters (because after the previous operation, the beginning here is certainly useful)
sHash[s[ss]-'a']--;
found--;
ss++;
}
}
return 0;
}```

After the game, I saw the code and found that it was easier, but the principle was the same
Code:

```#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e6+10;
char s[N];
int a[N];
int main(void){
scanf("%s",s);
int l=strlen(s);
//Number of characters matched
int num=0;
int ans=0x3f3f3f3f;
for(int i=0,j=0;i<l;i++){
if(!a[s[i]-'a']){
num++;
}
a[s[i]-'a']++;
while(num==26){
ans=min(ans,i-j+1);
a[s[j]-'a']--;
//Deletion of the beginning character of the substring has an effect
if(!a[s[j++]-'a']){
num--;
break;
}
}
}
printf("%d\n",ans);
return 0;
}```

Posted on Sun, 05 Jan 2020 13:19:03 -0800 by todd2006