eli和字符串

eli和字符串
https://ac.nowcoder.com/acm/contest/3002/G

大佬代码：
双指针区间维护

#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
char s[N];
int b[26];

int solve() {
    int n, k; scanf("%d%d%s", &n, &k, s);
    int mx = 0, ans = 2e9;
    int L = 0, R = 0;
    for (R = 0; R < n; ++R) {
        int t = s[R] - 'a';   
        ++b[t];  
        //cout << L <<' ' << R <<' '<<t << ' '<<b[t] << endl;
        if (b[t] == k) {
            while (L < R && s[L] != s[R]) {
                --b[s[L] - 'a']; ++L;  //--b[s[L] - 'a']-->在“第一个”==s[R]之前的字母必长于s[R]所对应的长度，故而排除
            }

            ans = min(ans, R - L + 1);
            --b[s[L] - 'a']; ++L;
        }
    }
    if (ans == 2e9) ans = -1;
    printf("%d\n", ans);
    return 0;
}

int main() {
    //int T; scanf("%d", &T); while(T -- )
    solve(); return 0;
}

蒟蒻代码
开26个前缀和，分别找其最小值。
唯一亮点可能就是 使用队列来进行存储位置，方便使得start=second了

#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;

int word[30];
char S[200010];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    getchar();
    for (int i = 0; i < n; i++) {
        scanf("%c", &S[i]);
        word[S[i] - 'a']++;
    }


    int flag = 0;
    for (int i = 0; i < 26; i++) {
        if (word[i] >= k) {
            flag = 1;
            break;
        }
    }
    if (!flag) {
        cout << "-1" << endl;
        return 0;
    }
    if (k == 1) {
        cout << "1" << endl;
        return 0;
    }

    int minn = n + 1;

    for (int i = 0; i < 26; i++) {
        int ans = 0;
        int start = -1;
        int cnt = 0;
        queue<int> Q;
        if (word[i] >= k) {
            for (int j = 0; j < n; j++) {


                if (k == 2) {
                    if (start == -1 && S[j] == i + 'a') {
                        start = j;
                        ans++;
                        cnt++;
                        continue;
                    }
                    if (S[j] == i + 'a') {
                        if (minn > j - start + 1) {
                            minn = j - start + 1;
                            ans--;
                            cnt++;
                            start = j;
                            continue;
                        }
                        cnt++;
                        ans--;
                        start = j;
                        continue;
                    }
                }

                if (start == -1 && S[j] == i + 'a') {
                    start = j;
                    ans++;
                    cnt++;
                    Q.push(j);
                    continue;
                }
                if (S[j] == i + 'a') {
                    ans++;
                    cnt++;
                    Q.push(j);
                    if (ans == k) {
                        Q.pop();
                        if (minn > j - start + 1) {
                            minn = j - start + 1;
                            start = Q.front();
                            ans--;
                        }
                        else {
                            start = Q.front();
                            ans--;
                        }
                    }
                }
            }
        }
    }
    cout << minn << endl;

}