Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- const int N = 100010;
- int n,k; //n = number of characters and k = how many character's you can change
- int pa[N],pb[N]; //pa => prefix sum of a,pb => pref sum of b
- bool yes (int x) {
- int L = 1,R = x;
- while (R <= n) {
- int a = pa[R] - pa[L - 1];
- int b = pb[R] - pb[L - 1];
- int m = min(a,b);
- if (m <= k) {
- //~ cout << L << ' ' << R << '\n';
- return true;
- }
- L++,R++;
- }
- //asbei na
- return false;
- }
- //1) calc pref
- //2) bin search
- //3) implement yes function
- int main () {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- string s;
- cin >> n >> k >> s;
- int a[n + 1],b[n + 1];//if ith pos contain a 1 otherwise 0
- a[0] = 0,b[0] = 0;
- for (int i = 0; i < n; ++i) {
- if (s[i] == 'a') {
- a[i + 1] = 1;
- } else {
- a[i + 1] = 0;
- }
- }
- for (int i = 0; i < n; ++i) {
- if (s[i] == 'b') {
- b[i + 1] = 1;
- } else {
- b[i + 1] = 0;
- }
- }
- for (int i = 1; i <= n; ++i) {
- pa[i] = pa[i - 1] + a[i];
- }
- for (int i = 1; i <= n; ++i) {
- pb[i] = pb[i - 1] + b[i];
- }
- int l = 1,r = n;
- int res = 0;
- while (l <= r) {
- int mid = (l + r) / 2;
- if (yes(mid)) {
- res = mid;
- l = mid + 1;
- } else {
- r = mid - 1;
- }
- }
- cout << res << '\n';
- }
- //Problem Link : https://codeforces.com/contest/676/problem/C
Add Comment
Please, Sign In to add comment