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; }