G eli和字符串 题解

本题其实用前缀和就可以做
因为每个字母出现一次，那么它的出现次数就+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，那么说明没有满足条件的情况】