题目描述:eli拿到了一个仅由小写字母组成的字符串。
她想截取一段连续子串,这个子串包含至少k个相同的某个字母
她想知道,子串的长度最小值是多少?
注:所谓连续子串,指字符串删除头部和尾部的部分字符(也可以不删除)剩下的字符串。
思路:利用for遍历26个字母,每个字母利用尺取法查找满足条件的最小长度。
AC代码如下:

#include <iostream>
#include <map>
using namespace std;

const int INF = 1e7 + 5;
const int MAXX = 2e5 + 5;
map<char, int> mp;

int main() {
    ios::sync_with_stdio(false);

    int n, k;
    char s[MAXX];
    cin >> n >> k >> s;
    for (int i = 0; i < n; i++) {
        mp[s[i]]++;
    }

    int pl, pr, ans = INF;
    for (int i = 97; i <= 97 + 26; i++) {  //遍历26个字母
        if (mp[i] >= k) {      //判断该字母是否满足出现大于等于K
            int l = 0, r = 0;  // l,r记录当前的左右边界
            int cut = 0;  // cut记录下标i表示的字母在区间[l,r]出现的次数
            if (s[r] == i) cut++;

            while (true) {
                if (cut == k) {  //出现k次
                    if (ans > r - l + 1) {  //判断当前ans长度和该子串长度的大小关系
                        ans = r - l + 1;
                        pl = l, pr = r;
                    }
                    if (s[l] == i) cut--;
                    l++;  //左边界右移
                } else {
                    if (r == n - 1) {  //右边界不能再向右了
                        break;
                    }
                    r++;
                    if (s[r] == i) cut++;
                }
            }
        }
    }

    if (ans == INF) {
        cout << "-1\n";
    } else {
        cout << pr - pl + 1 << endl;
    }
    return 0;
}