problem

给出一个长度为的字符串，求出他的一个最短子串，要求这个子串里面包含了全部个小写英文字母。

solution

统计出每个位置到后面每种字符的最近距离。其中的最大值就是以当前位置为起点的答案。

用当前最靠前的字符所在的位置，然后从前往后扫，对于每个位置都统计一下答案即可。

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int lst[100];
char s[N];
int main() {
    scanf("%s",s + 1);
    memset(lst,0x3f,sizeof(lst));
    int n = strlen(s + 1);
    int ans = 1e9;
    for(int i = n;i >= 1;--i) {
        lst[s[i] - 'a'] = i;
        int ret = 0;
        for(int j = 0;j < 26;++j) {
            ret = max(ret,lst[j] - i);            
        }
        ans = min(ans,ret + 1);
    }
    cout<<ans<<endl;
    return 0;
}