G-eli题解报告

简单的队列模拟

首先把每一个字母加入队列，我们用head，tail表示队列的头和尾
head是头的后一位，tail是尾
那么目前所查找的区间长度为tail-head+1， tail=head+1时队列为空
我们先不断地加入字母(按顺序)
直到其中出现重复的k个字母，这时候就要把头缩回来(++head)，直到头是这个字母为止，那么我们认为以这个字母为头和尾的字串是目前查找的最短的字串
那么在头缩进去的时候，会失去一些其他的字母，但很明显，目前来看的队列长度是len，而这些字母为首能组成的k个字母重复的字串明显是>len的，而以当前字母为尾的k个重复的字串还在缩头过程中，必定<len
重复做这些操作，比较最大值即可

贴上蒟蒻代码：

#include<bits/stdc++.h>
#define maxn 200010
#define INF 9999999
using namespace std;

int n,k,ans=INF;
int que[maxn],head=1,tail=0;
int num[30];
string str;

int main(){
    scanf("%d%d",&n,&k);
    cin>>str;
    for(int i=0;i<n;++i){
        int j=int(str[i])-'a'+1;
        que[++tail]=j; 
        num[j]++;
        if(num[j]==k){
            while(head<tail+1){
                if(que[head]==j){
                    ans=min(ans,tail-head+1);
                    --num[j];
                    ++head;
                    break;
                }
                else --num[que[head]],++head;
            }
        }
    }
    if(ans==INF) printf("-1");
    else printf("%d",ans);
    return 0;
}