BTSTRT4 - Editorial

editorial
,
1

Problem Link

Setter: Rahul Kumar
Tester: Aniket Kumar
Editorialist: Rahul Kumar

DIFFICULTY:
SIMPLE - EASY

PROBLEM:
Given a string of length N which contains only A or B characters. A good string is the one in which all the characters are same. You need to find the longest substring that is a good string by doing the one of the following operation only once.

  • Choose a good substring and subtract 1 from all the characters of this substring.
  • or add 1 to all the characters of this substring.

Subtracting 1 from a character means replacing it with a letter below it for e.g. B-1=A, D-1=C. And adding 1 means replacing it with letter above it for e.g. B+1=C, X+1=Y.
Print the max length of good substring after the operation.
Print minimum XOR.

EXPLANATION:
We will store the frequency of letter for every continuous characters in an array.
Then we will traverse the array checking maximum value of A[i-1] + A[i] + A[i+1] .
So that the operation can be performed in the A[i] part to make the characters same.

TIME COMPLEXITY:
O(N)

SOLUTION:

#include<bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int 
#define vi vector<int>
#define w(x) int x; cin>>x; while(x--)
#define pb push_back
#define print(v) for(int i=0;i<v.size();i++) cout<<v[i]<<" "; 

int32_t main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    fio
    w(t)
    {
        int n;
        cin>>n;
        vi p;
        string v;
        cin>>v;
        char c=v[0]; /*storing any of the two letters*/
        int o=0,z=0;
        for(int i=0;i<n;i++)
        {
            if(v[i]==c)
            {
                z++;
                if(o>0)
                {
                    p.pb(o); /*storing no. of 2nd letter when transition from 2nd  to 1st*/
                    o=0;
                }
            }
            else
            {
                o++;
                if(z>0)
                {
                    p.pb(z); /*storing no. of 1st letters when transition from 1st to 2nd */ 
                    z=0;
                }
            }
            /*When reaches last index*/
            if(i==n-1)
            {
                if(z>0)
                {
                    p.pb(z); z=0;
                }
                else if(o>0)
                {
                    p.pb(o); o=0;
                }
            }
        }
        int m=0;
        for(int i=0;i<p.size()-1;i++)
        {
            if(i==0)
            {
                m=max(p[i]+p[i+1],m);
            }
            else if(i==n-1)
            {
                m=max(p[i]+p[i-1],m);
            }
            else
                m=max(p[i-1]+p[i]+p[i+1],m);
        }
        cout<<m<<"\n";
    }
}

Please comment below if you have any questions, alternate solutions, or suggestions. :slightly_smiling_face: