题目描述:eli拿到了一个仅由小写字母组成的字符串。 她想截取一段连续子串,这个子串包含至少 个相同的某个字母。 她想知道,子串的长度最小值是多少? 注:所谓连续子串,指字符串删除头部和尾部的部分字符(也可以不删除)剩下的字符串。
思想:队列,结构体,字符串脚标的计数
总是出错的原因:
1、开辟的二维数组过大(记录路径的 ll path[30][200010])
解决:改为结构体数组,通过在结构体内定义一位数组记录路径
2、字符串脚标总是搞错
解决:注意长度,脚标的关系,长度用结构体中的 ll length定义计算更方便;
3、可以直接用“字符相减”的方式来计数,不用算出ASCII值
include<bits/stdc++.h>
define ll long long
using namespace std;
struct letter
{
ll path[200009];
ll length=0;
}letter[26];
int main()
{
ll n,k,minx=1000000;
char a[200010];
cin>>n>>k>>a;
for(int j=0;j<n;j++)
{
int m=a[j]-'a';
letter[m].length++;
letter[m].path[letter[m].length-1]=j;
}
for(int i=0;i<26;i++)
{
if(letter[i].length>=k)
{
for(int j=0;j<letter[i].length-k+1;j++)
{
minx=min(minx,(letter[i].path[j+k-1]-letter[i].path[j]+1));
}
}
}
if(minx!=1000000)
cout<<minx<<endl;
else cout<<"-1"<<endl;
return 0;
}