题目描述: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; }