本题其实用前缀和就可以做
因为每个字母出现一次,那么它的出现次数就+1,所以记录它的每个出现位置,用数组trace记录
具体做法:
struct node
{
int trace[200010], index=1;
} lt[26];
【trace类似于vector,莫习惯这么写了,见谅】
由于要求同个字母出现次数至少为k次的子段,不难证明即为要求同个字母出现k次的子段
这时候只要在刚刚记录下的trace中暴力找就好了
而其中lt记录下了所有字母的trace,所以暴力不会漏掉任意一种情况
时间复杂度(本蒟蒻不会算)估计大概是O(26*(n-k)),不会炸
附上完整代码:
#include<bits/stdc++.h>
using namespace std;
struct node
{
int trace[200010], in=1;
} sum[30];
int main()
{
int n, k; cin>>n>>k;
string s; cin>>s;
for (int i=0; i<s.length(); i++)
{
int c = s[i] - 'a';
sum[c].trace[sum[c].in++] = i;
}
int ans = 10000010;
for (int i=0; i<26; i++)
{
for (int j=1; j<=sum[i].in-k; j++) ans = min(ans, sum[i].trace[j+k-1]-sum[i].trace[j]+1);
}
if (ans != 10000010) cout<<ans;
else cout<<-1;
}【其中的10000010类似于inf,如果找完一轮后ans还是inf,那么说明没有满足条件的情况】

京公网安备 11010502036488号