EASYABC - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest-Link

Author: Yash Dwivedi
Tester: Shubham Kushwaha
Editorialist: Shubham Kushwaha

DIFFICULTY:

EASY

PREREQUISITES:

String

PROBLEM:

You are given a string of length n consisting only of characters ‘a’, ‘b’ or ‘c’ where 1 <= n <= 10^5 . You have to find the maximum value of the absolute difference between i and j i.e abs(i-j) where s[i] != s[j] and 1<=i,j<=10^5.

QUICK EXPLANATION:

The maximum difference between indexes will be either between the rightmost character different from the first character or the difference between the leftmost character different from the last character.

EXPLANATION:

It was a basic observation-based question where we needed a greedy approach. It is clear that the distance between the rightmost character different from the first character or the distance between the leftmost character different from the last character will be the maximum distance.
We have to traverse the array twice and find both the distances and print the maximum between the two.
Time complexity will be O(n) where n is the length of the string.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
int main() 
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--)
    {               
      ll n,i;
     string a;
     cin>>a;
     n=a.size();
     {  
       ll mx=0,mx2=0;
       for(i=1;i<n;i++)
       {
        if(a[i]!=a[0])
       mx=i;
       }
       for(i=n-2;i>=0;i--)
       {
       if(a[i]!=a[n-1])
       mx2=n-1-i;
       }
       cout<<max(mx,mx2)<<endl;
      }
   }
    return 0; 
}
Tester's Solution 
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cctype>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <sstream>
#include <complex>
#include <fstream>
#include <functional>
#include <numeric>
#include <utility>
#include <algorithm>
#include <assert.h>
#include <unordered_map>
using namespace std;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define endl '\n'
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ai(arr,n) for(int i=0;i<n;i++)cin>>arr[i];
#define ao(arr) for(auto asdfasdfasdf:arr) cout<<asdfasdfasdf<<" ";
#define mi(arr,m,n) for(int i=0;i<m;i++){ for(int j=0;j<n;j++) cin>>arr[i][j];}
#define mo(arr,m,n) for(int i=0;i<m;i++){ for(int j=0;j<n;j++) cout<<arr[i][j]<<" "; cout<<endl;}
#define countsetbits(x) __builtin_popcount(x)
#define ll long long
#define debug cout<<"I AM EXECUTING"<<endl
#define testcases int asdf; cin>>asdf; while(asdf--)
#define vi vector<int>
#define vll vector<long long int>
#define vppo(prs) for(auto x:prs){cout<<x.first<<" "<<x.second<<endl;}
#define For(__,hajmola,adfdf) for(int __ = hajmola; __<adfdf;__++)
 string sconvert(ll int n)
{
stringstream ss;
ss<<n;
string str = ss.str();
return str;
}
bool sortbysec(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second > b.second);
}
 
template<typename T>
void imax(T &x,T y){
x = max(x,y);
}
template<typename T>
void imin(T &x,T y){
x = min(x,y);
}
const int nax = 10000;
void single()
{
string str;
cin>>str;
ll int n=str.length();
string temp = "abc";
ll int answer=INT_MIN;
for(int i=0;i<temp.size();i++){
for(int j=0;j<temp.size();j++){
if(temp[i]!=temp[j]){
ll int minind=INT_MAX;
ll int maxind = INT_MIN;
for(ll int t=0;t<n;t++){
if(str[t]==temp[i]){
imin(minind,t);
}
if(str[t]==temp[j]){
imax(maxind,t);
}
}
if(maxind==INT_MIN or minind==INT_MAX)
continue;
imax(answer,abs(maxind-minind));
}
}
}
cout<<answer<<endl;
return;
}
void multiple()
{
testcases
{
single();
}
}
int main()
{
IOS;
// freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
single();
}
Editorialist's Solution 
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cctype>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <sstream>
#include <complex>
#include <fstream>
#include <functional>
#include <numeric>
#include <utility>
#include <algorithm>
#include <assert.h>
#include <unordered_map>
using namespace std;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define endl '\n'
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ai(arr,n) for(int i=0;i<n;i++)cin>>arr[i];
#define ao(arr) for(auto asdfasdfasdf:arr) cout<<asdfasdfasdf<<" ";
#define mi(arr,m,n) for(int i=0;i<m;i++){ for(int j=0;j<n;j++) cin>>arr[i][j];}
#define mo(arr,m,n) for(int i=0;i<m;i++){ for(int j=0;j<n;j++) cout<<arr[i][j]<<" "; cout<<endl;}
#define countsetbits(x) __builtin_popcount(x)
#define ll long long
#define debug cout<<"I AM EXECUTING"<<endl
#define testcases int asdf; cin>>asdf; while(asdf--)
#define vi vector<int>
#define vll vector<long long int>
#define vppo(prs) for(auto x:prs){cout<<x.first<<" "<<x.second<<endl;}
#define For(__,hajmola,adfdf) for(int __ = hajmola; __<adfdf;__++)
 string sconvert(ll int n)
{
stringstream ss;
ss<<n;
string str = ss.str();
return str;
}
bool sortbysec(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second > b.second);
}
 
template<typename T>
void imax(T &x,T y){
x = max(x,y);
}
template<typename T>
void imin(T &x,T y){
x = min(x,y);
}
const int nax = 10000;
void single()
{
string str;
cin>>str;
ll int n=str.length();
string temp = "abc";
ll int answer=INT_MIN;
for(int i=0;i<temp.size();i++){
for(int j=0;j<temp.size();j++){
if(temp[i]!=temp[j]){
ll int minind=INT_MAX;
ll int maxind = INT_MIN;
for(ll int t=0;t<n;t++){
if(str[t]==temp[i]){
imin(minind,t);
}
if(str[t]==temp[j]){
imax(maxind,t);
}
}
if(maxind==INT_MIN or minind==INT_MAX)
continue;
imax(answer,abs(maxind-minind));
}
}
}
cout<<answer<<endl;
return;
}
void multiple()
{
testcases
{
single();
}
}
int main()
{
IOS;
// freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
single();
}
2

My code was exactly the above idea however i solved it in just one loop.
Link to my code: click here!

1 Like
3

Yeah checking all the different character combination of string “abc” is also a good approach :+1:

1 Like
4

For video editorial, you can watch this live stream by Nikita Skybytskyi @sky_nik video link.
Thanks @sky_nik for this live stream.