NC18386 字符串（尺取）

题意

小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的，当且仅当T中包含了所有的小写字母。小N希望知道所有的合法的S的子串中，长度最短是多少。 。

分析

对每个 ，我们要求最大的 ，使得 包含了所有小写字母。
显然， 是单调递增的。
于是我们开个桶记录一下每个字母出现了多少次，从左到右扫一遍即可。
时间复杂度是

代码如下

#include <bits/stdc++.h>

using namespace std; 

const int N = 1e6 + 5;
char s[N];
int cnt[255];

int main(){
    int i, j, n, m, tot = 0, ans = 1e9;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    j = 1; cnt[s[1]]++; tot = 1;
    for(i = 2; i <= n; i++){
        if(!cnt[s[i]]) tot++;
        cnt[s[i]]++;
        while(cnt[s[j]] > 1){
            cnt[s[j]]--;
            j++;
        }
        if(tot == 26) ans = min(ans, i - j + 1);
    }
    printf("%d", ans);
    return 0;
}