第一行两个正整数和
，分别代表字符串的长度、和妹红按下按钮的次数。
第二行为一个仅由字符“0”和“1”组成的字符串。
妹红至少按
6 2 001100
8
注意到k=2，因此要寻找最少按2次就能打印的子串。s[0,2]="001"，妹红最少按2次就能按出来，先按0再按1。s[0,3]="0011"，妹红最少按2次就能按出来，先按0再按1。
s[1,2]="01"，妹红最少按2次就能按出来，先按0再按1。
s[1,3]="011"，妹红最少按2次就能按出来，先按0再按1。
s[2,4]="110"，妹红最少按2次就能按出来，先按1再按0。
s[2,5]="1100"，妹红最少按2次就能按出来，先按1再按0。
s[3,4]="10"，妹红最少按2次就能按出来，先按1再按0。
s[3,5]="100"，妹红最少按2次就能按出来，先按1再按0。
共有8个子串符合要求。
3 1 110
4
注意到k=1，因此要寻找按1次就能打印的子串。s[0,0]="1"，妹红按住1就可以打印出来，只按了1次按钮s[0,1]="11"，妹红按住1就可以打印出来，只按了1次按钮
s[1,1]="1"，妹红按住1就可以打印出来，只按了1次按钮
s[2,2]="0"，妹红按住0就可以打印出来，只按了1次按钮
共有4个子串符合要求。
对于20%的样例，
对于40%的样例，
对于60%的样例，
对于100%的样例，
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
s = ' ' + s;
ll cnt = 0, ans = 0;
for (int l = 1, r = 1; r <= n; r++) {
cnt += (s[r] != s[r - 1]);
while (cnt > k) {
cnt -= (s[l] != s[l + 1]);
l++;
}
ans += r - l + 1;
}
if(k>1){
cnt = 0;
for (int l = 1, r = 1; r <= n; r++) {
cnt += (s[r] != s[r - 1]);
while (cnt > k - 1) {
cnt -= (s[l] != s[l + 1]);
l++;
}
ans -= r - l + 1;
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
双指针写法
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
