PROBLEM LINK:
PRACTICE
Editorialist: Indrajit Kabiraj
DIFFICULTY:
MEDIUM
PREREQUISITES:
Strings
PROBLEM:
Chef is an administrator of Codechef. He has come to know that cheating is going on his platform. He has a record of users as a binary string, where ‘0’ means the user has not cheated. So he wants to ban those cheaters but he may or may not be able to ban all the cheaters. He can only ban a cheater if he has no other cheater on his adjacent. Eg: 101011101011 He can ban 22 cheaters, indexes are [1,3][1,3]. You as a friend of the chef can alter the record of the chef’s record by inverting at most 11 character from the string(changing ‘1’ to ‘0’ or vice versa). Chef wants to know the longest substring where consecutive characters are different.
EXPLANATION:
In this question, we just need to find the largest substring of alternating characters.
Hence, we first store the largest substring of alternating characters without changing any letter in the string.
As we can change only invert only one character and the constraint was low so brute force approach is sufficient.
For each character, we will invert it and find the largest substring of alternating characters and the maximum of it will be the result.
SOLUTION:
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
string s;
cin>>n>>s;
int res = 0,mx = 0;
char last = s[0];
if(n==1){
cout<<1<<endl;
continue;
}
for(int i=0;i<n;i++){
mx = 0;
if(s[i]=='0'){
s[i]='1';
}
else{
s[i]='0';
}
int cnt=1;
last = s[0];
for(int j=1;j<n;j++){
if(s[j]!=last){
cnt++;
}
else{
mx = max(mx,cnt);
cnt=1;
}
mx = max(mx,cnt);
last = s[j];
}
if(s[i]=='0'){
s[i] = '1';
}
else{
s[i] = '0';
}
res = max(res,mx);
last = s[0];
cnt=1;
mx = 0;
for(int j=1;j<n;j++){
if(s[j]!=last){
cnt++;
}
else{
mx = max(mx,cnt);
cnt=1;
}
last = s[j];
mx = max(mx,cnt);
}
res = max(res,mx);
}
cout<<res<<endl;
}
}