#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> typedef long long ll; using namespace std; struct node { int trace[200010]; //记录的是第in+1个字母'c'出现的位置 int in=0; //记录字母‘c‘出现的位置 } sum[30]; //一共26个小写字母,从0开始记 int main() { int n, k; //n表示字符串的个数,k表示要求包含k个相同字符 cin >> n >> k; string s; cin >> s; /* 以abeba为例,初始化 i=0; c=a-a=0; sum[0].trace[1]=0,sum[0].in=2; i=1; c=b-a=1; sum[1].trace[1]=1,sum[1].in=2; i=2; c=e-a=4; sum[4].trace[1]=2,sum[4].in=2; i=3; c=b-a=1; sum[1].trace[2]=3,sum[1].in=3; i=4; c=a-a=0; sum[0].trace[2]=4,sum[0].in=3; 最后的结果: 对字母a: 位置(i): 0 1 2 3 4 5 6 7 8 9 sum[0].trace[i]: 0 4 sum[0].in 最后是3 对字母b: 位置(i): 0 1 2 3 4 5 6 7 8 9 sum[1].trace[i]: 1 3 sum[1].in 最后是3 对字母e: 位置(i): 0 1 2 3 4 5 6 7 8 9 sum[4].trace[i]: 2 sum[4].in 最后是2 */ for (int i=0; i<s.length(); i++) { int c = s[i] - 'a'; sum[c].trace[++sum[c].in] = i; } int ans = 10000010; //ans表示包含k个相同字符的最小长度 for (int i=0; i<26; i++) //记录a是0,所以记录字符是从0开始,25结束 { for (int j=1; j<=sum[i].in-k+1; j++) { ans = min(ans, sum[i].trace[j+k-1]-sum[i].trace[j]+1); //第j+k-1次出现的位置 - 第j次出现的位置(一共出现k次) } } if (ans != 10000010) cout << ans << endl; else cout << "-1" << endl; return 0; }