GDUT B.过生日

发布于 2021-11-28  13 次阅读


题目概述

思路

使用队列思想,将每一个字符的编号存储到每一个字符所对应的队列,当队列的元素达到了我们想要的k时,我们可以将这个子串的长度和ans比较,保留最小的解并输出,不存在则输出-1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath> 
#include<queue>
#include<algorithm>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int t;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        queue<int> q[150];
        int k,ans=INF;
        string s;
        cin>>s>>k;
        for(int i=0;i<=s.size();++i)
        {
            q[int(s[i])].push(i);
            if(q[int(s[i])].size()==k)
            {
                ans=min(ans,i-q[int(s[i])].front()+1);
                q[s[i]].pop();
            }
        }
        if(ans==INF)
            printf("-1\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}