题目描述: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;
}
京公网安备 11010502036488号