Wannafly challenge 23A - string

Links: https://www.nowcoder.com/acm/contest/161/A
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[26];
int tHash[26];
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++;
            }
            //Update answers
            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