题解 | eli和字符串

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1145141919810; // 初始化无穷大，用于记录最小长度的初始值

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 关闭同步，加速输入输出
    ll n,k;
    cin>>n>>k;
    string s;
    cin>>s;

    // ********** 初始化算法核心变量 **********
    // 哈希表：key=字符，value=该字符出现的所有下标（按出现顺序存储）
    unordered_map<char,vector<ll>>m;
    ll ans=inf; // 记录满足条件的子串最小长度，初始为无穷大

    // ********** 核心：遍历字符串，维护每个字符的出现位置列表 **********
    for(ll i=0;i<n;i++){
        // 步骤1：将当前字符的下标i加入对应字符的位置列表
        m[s[i]].emplace_back(i);

        // 步骤2：如果当前字符的出现次数超过k，删除最早的下标（仅保留最近k个位置）
        // 原因：我们需要的是「包含恰好k个该字符」的子串，保留最近k个位置才能得到最短子串
        if(m[s[i]].size()>k){
            m[s[i]].erase(m[s[i]].begin());
        }

        // 步骤3：当当前字符的出现次数恰好为k时，计算对应子串的长度
        if(m[s[i]].size()==k){
            // 子串的左边界是列表中第一个下标，右边界是列表中最后一个下标
            // 子串长度 = 右边界 - 左边界 + 1（下标从0开始，+1是因为要包含两端）
            ll t=m[s[i]].back()-m[s[i]].front()+1;
            ans=min(ans,t); // 更新全局最小长度
        }
    }

    // ********** 输出结果 **********
    if(ans==inf)cout<<-1; // 若ans仍为无穷大，说明没有字符出现至少k次，输出-1
    else cout<<ans; // 否则输出最小子串长度
	return 0;
}