In this HackerEarth uniformity problem solution, You are given a string that contains only three characters a, b, and c. You can change at the most k characters in the string. The uniformity index of a string is defined by the maximum length of the substring that contains the same character. Your task is to determine the maximum uniformity index that can be achieved.
HackerEarth Uniformity problem solution.
#include <bits/stdc++.h>
#define ld long double
#define inf -2
using namespace std;
int main(){
int c1 = 0;
int c2 = 0;
int c3 = 0;
int n,k;
cin>>n>>k;
string s;
cin>>s;
int l=0,r=-1;
int ans =0;
vector<int>temp(3);
while(l<n){
while(r<n-1){
r++;
if(s[r]=='a'){
c1++;
}else if(s[r]=='b'){
c2++;
}else{
c3++;
}
temp[0] = c1;
temp[1] = c2;
temp[2] = c3;
sort(temp.begin(),temp.end());
int mi = temp[0]+temp[1];
if(mi>k){
break;
}
//cout<<l<<" "<<r<<" "<<c1<<" "<<c2<<"n";
ans = max(ans,c1+c2+c3);
}
if(s[l]=='a'){
c1--;
}else if(s[l]=='b'){
c2--;
}else{
c3--;
}
l++;
}
cout<<ans;
}
Second solution
#include<bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define vll vector<ll>
#define llin(a) ll a; cin>>a;
#define llin2(a,b) ll a,b; cin>>a>>b;
#define llin3(a,b,c) ll a,b,c; cin>>a>>b>>c;
#define fulll(v) v.begin(),v.end()
#define vecin(n, v) for(ll i=0; i<n;i++) cin>>v[i];
#define vecout(n, v) for(ll i=0; i<n;i++) cout<<v[i]<<" "; cout<<endl;
#define rep(i, s, n) for(ll i=(ll)s;i<(ll)n;i++)
#define rrep(i, s, n) for(ll i=(ll)s;i>=(ll)n;i--)
#define pb push_back
#define mkp make_pair
#define endl "n"
#define test cout<<"test line"<<endl;
#define swapper void swap(ll *a, ll *b){ll t=*a;*a=*b;*b=t;}
#define pll pair<ll,ll>
#define vpll vector<pll >
#define modexp ll power(ll x, ll y, ll p){ int res = 1; x = x % p; while(y>0){ if(y&1) res = (res*x) % p; y = y>>1; x = (x*x) % p; } return res; }
#define psieve void sieve(){ memset(prime, true, sizeof(prime)); for(ll p=2; p*p<=maxn; p++) if (prime[p]) for (ll i=p*2; i<=maxn; i+= p) prime[i] = false; }
#define mod 1000000007
#define INF 0x3f3f3f3f
#define MAX 1000000000
using namespace std;
ll n, k;
string s;
ll solve(char ch){
ll mx=0, h1=0, h2=0;
for(ll i=0, j=0; j<n;){
assert(s[j]=='a' || s[j]=='b' || s[j]=='c');
if(h2 > k)
s[i++]==ch?h1--:h2--;
else{
mx = max(mx, h1+h2);
s[j++]==ch?h1++:h2++;
}
}
if(h2 <= k)
mx = max(mx, h1+h2);
return mx;
}
int main(){
fast
cin>>n>>k;
assert(n>=1 && n<=1000000);
assert(k>=0 && k<=n);
cin.ignore();
cin>>s;
cout<<max(solve('a'), max(solve('b'), solve('c')));
return 0;
}