题目大意:给你个全部小写英文字母的字符串,问你子串中包含26个英文小写字母的最短子串是多少
思路:直接尺取法,一开始右指针一直往右移动直到子串符合要求,符合要求后左指针再向右移动以去掉重复字母得到子串的长度,之后再重复流程,利用一个变量储存最小长度即可
代码如下:
#include <iostream>
#include <string.h>
#include <cstdio>
#include <map>
using namespace std;
char s[1000010];
int c[26]= {0};//记录每个小写字母的出现次数
int main()
{
cin>>s;
int cnt=0;//记录出现了多少种英文字母的变量
int ans=10000000;
int n=0;
int i=0;//i为左边界,n为右边界
int len=strlen(s);
// cout<<'z'-'a'<<endl;
while(i<len)
{
while(n<len&&cnt<26)//防止n越界
{
if(c[s[n]-'a']==0)
cnt++;
c[s[n++]-'a']++;
}
if(n-i<ans&&cnt==26)ans=n-i;
if(c[s[i]-'a']==1)
cnt--;
c[s[i++]-'a']--;
}
cout<<ans;
return 0;
}
京公网安备 11010502036488号