HackerEarth Monk and Chocolates problem solution

In this HackerEarth Monk and Chocolates problem solution Monk loves to eat chocolates. Out of his love for chocolates, he went to Chocoland. Chocoland is an amazing place for chocolate lovers. There are many games played where prizes are given in form of chocolates. Monk being an avid choco fan decided to participate in one of the games.

In this game, we are given a string consisting of English letters. Each of these letters correspond to a unique chocolate. Now there are some rules in the game. A participant can change one of the letters in the sequence and make it to represent some other type of chocolate. This move is called a magic move. Each game has some fixed number of magic moves allowed and will be given in the question itself. We need to find the maximum length of consecutive characters of the string where all letters denote the same chocolate.

On correctly guessing the maximum length winner will be awarded those chocolates. Can you help Monk to win this contest?

HackerEarth Monk and Chocolates problem solution.

#include<bits/stdc++.h>
using namespace std;

#define TRACE
#ifdef TRACE
#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define TR(...)
#endif

typedef long long               LL;
typedef pair<int,int>           II;
typedef vector<int>             VI;
typedef vector<II>              VII;


#define REP(i,i1,n)             for(int i=i1;i<n;i++)
#define REPB(i,i1,n)            for(int i=i1;i>=n;i--)
#define PB                      push_back
#define MP                      make_pair
#define ALL(c)                  (c).begin(),(c).end()
#define F                       first
#define S                       second
#define log2                    0.30102999566398119521373889472449L
#define SZ(a)                   (int)a.size()
#define EPS                     1e-12
#define MOD                     1000000007
#define FAST_IO                 ios_base::sync_with_stdio(false);cin.tie(NULL)
#define SI(c)                   scanf("%d",&c)
#define SLL(c)                  scanf("%lld",&c)
#define PIN(c)                  printf("%dn",c)
#define PLLN(c)                 printf("%lldn",c)
#define N                       200010
#define endl                    'n'
#define FILL(ar,vl)             for(int i=0;i<N;i++)ar[i]=vl
#define FILL2(ar,vl)            for(int i=0;i<N;i++)for(int j=0;j<N;j++)ar[i][j]=vl

inline int mult(int a , int b) { LL x = a; x *= LL(b); if(x >= MOD) x %= MOD; return x; }
inline int add(int a , int b) { return a + b >= MOD ? a + b - MOD : a + b; }
LL powmod(LL a,LL b) { if(b==0)return 1; LL x=powmod(a,b/2); LL y=(x*x)%MOD; if(b%2) return (a*y)%MOD; return y%MOD; }

bool check(int mid, string s, int k) {
    int cnt[52];
    memset(cnt, 0, sizeof(cnt));
    REP(i,0,s.size()) {
        REP(j,0,52) {
            if(s[i] - 'A' <= 25) {
                if(s[i] - 'A' != j) {
                    cnt[j] ++;
                }
            }
            else {
                if(s[i] - 'a' + 26 != j) {
                    cnt[j] ++;
                }
            }
            if(i >= mid - 1) {
                if(cnt[j] <= k) return true;
                
                if(s[i - mid + 1] - 'A' <= 25) {
                    if(s[i - mid + 1] - 'A' != j) cnt[j] --;
                }
                else {
                    if(s[i - mid + 1] - 'a' + 26 != j) cnt[j] --;
                }
            }
        }
    }
    return false;
}

int main() {    
    int t;
    cin>>t;
    while(t--) {
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int lo = 1, hi = s.size(),ans = 1;
        while(lo <= hi) {
            int mid = (lo + hi)/2;
            bool f = check(mid, s, k);
            if(f) {
                ans = mid;
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        cout<<ans<<"n";
    }
}

coding problems solutions