STR_REVERSE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Hitesh Jindal
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Chef has a string S consisting only of English lowercase letters (a - z). However, Hitesh does not like it and wants it to be reversed.

Hitesh wonders what is the minimum number of operations required to reverse the string S using the following operation:

  • Select any i such that 1 \le i \le \lvert S \rvert and remove S_i from its original position and append it to the end of the string (i.e. shift any character to the end of the string).

For e.g. if S = abcde and we apply operation on i = 2, then S becomes acdeb.

Help Hitesh find the minimum number of operations required to reverse S.

It is guaranteed that it is possible to reverse the string in a finite number of operations.

QUICK EXPLANATION:

  • In the optimal scenario, we will never remove the same character twice. In this sentence, we are treating each index element as a distinct character. So, in aba, the first and the third a are distinct for this sentence.
  • Let S' denote the set of indices (in the original string) that we have removed and appended at the end, and let S denote the set of indices that we have not operated on. How will the string look after all the operations.
  • Make the cardinality of S as large as possible.

EXPLANATION:

The first observation is in the optimal scenario, we should never remove the same character twice. To see this, consider a sequence of operations O_1 in which the same character c is removed twice. Consider another sequence of operations O_2, where the first operation in which the character c was removes, is removed from O_1, and rest everything remains same. We can see that both O_1 and O_2 will lead to same string, with |O_2| < |O_1|.

Let S = \{i_1, i_2, ... , i_k\} be the set of indices which have not been operated on. Let us call the new string as new\_str. We have:

str = s_1s_2...s_n
rev\_str = s_ns_{n-1}...s_2s_1
new\_str = s_{i_1}s_{i_2}...s_{i_k} s_{i_1'}...,

Because rev\_str = new\_str, we have s_n = s_{i_1}, s_{n-1} = s_{i_2}, and so on. So to minimize the size of set S', we should maximize the size of set S, which is equal to k. In other words, we need to find out the longest prefix of rev\_str that appears as a subsequence in str.

We can find this prefix greedily, using the algorithm described here in O(N) time.

TIME COMPLEXITY:

O(N) per test case.

SOLUTION:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
 
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;

const ll mod = 998244353;

ll po(ll x, ll n ){ 
    ll ans=1;
     while(n>0){
        if(n&1) ans=(ans*x)%mod;
        x=(x*x)%mod;
        n/=2;
     }
     return ans;
}


void solve()
{   

    string s = readStringLn(1, 1e5);

    for(auto h:s) assert(h>='a' && h<='z');

    string t = s;
    reverse(t.begin(), t.end());

    int l=0;

    int n = s.length();
    sum_len += n;
    max_n = max(max_n, n);

    rep(i,n){
        if(s[i]==t[l]) l++;
    }

    cout<<n-l<<'\n';


}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,1000);
        
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
   
    assert(getchar() == -1);
    assert(sum_len<=2e5);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_len << '\n';
    cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    //cerr<<"Answered yes : " << yess << '\n';
    //cerr<<"Answered no : " << nos << '\n';
}
Tester's Solution 
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
 
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;

const ll mod = 998244353;

ll po(ll x, ll n ){ 
    ll ans=1;
     while(n>0){
        if(n&1) ans=(ans*x)%mod;
        x=(x*x)%mod;
        n/=2;
     }
     return ans;
}


void solve()
{   

    string s = readStringLn(1, 1e5);

    for(auto h:s) assert(h>='a' && h<='z');

    string t = s;
    reverse(t.begin(), t.end());

    int l=0;

    int n = s.length();
    sum_len += n;
    max_n = max(max_n, n);

    rep(i,n){
        if(s[i]==t[l]) l++;
    }

    cout<<n-l<<'\n';


}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,1000);
        
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
   
    assert(getchar() == -1);
    assert(sum_len<=2e5);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_len << '\n';
    cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    //cerr<<"Answered yes : " << yess << '\n';
    //cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution 
#include<bits/stdc++.h>
#define ll long long
using namespace std ;
const ll z = 998244353 ;


 
void solve()
{
    string str , orig;
    cin >> orig ;
    str = orig ;

    reverse(str.begin() , str.end()) ;

    int cnt = 0, n = str.size() ;
    for(int i = 0 ; i < n ; i++)
    {
        if(orig[i] == str[cnt])
            cnt++ ;
    }
    cout << n-cnt << endl ;
    return ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif

    ll t;
    cin >> t ;
    while(t--)
    {
        solve() ;
    }

    return 0;
}
4 Likes
2

I think there is no need to reverse the string. We can do it like this-

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define endl '\n'
#define fastIO() cin.tie(0)->sync_with_stdio(0);

int main() {
    fastIO();
	int TC = 1;
    cin >> TC;
	while (TC--) {
		string s;
		cin >> s;
		int cnt = 0, n = (int)s.length();
		for (int i = 0; i < n; i++) {
			if (s[i] == s[n - cnt - 1]) ++cnt;
		}
		cout << n - cnt << endl;
    }
	return 0;
}
4 Likes
3

Yes it works without reversing string.

4

I am not able to understand this part of the editorial, Can anyone explain, what is the meaning of this part?
@lavish_adm

5

what’s the logic behind subtracting cnt please explain bit??

6

I see its running alright. Can you please give me the logic or any article link maybe? Thank you.

1 Like
8

#include
#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
string s;
cin>>s;
int len=0;
len=s.length();
int step=0;
for(int i=0; i<(len/2); i++)
{
if(s[i]!=s[(len-1)-i]){
swap(s[i],s[(len-1)-i]);
step++;
}
}
cout<<step<<’\n’;
cout<<s<<’\n’;
}
return 0;
}

//bro ye work ku nhi kr rha is challenge ke liye

9

You have to find the min steps to reverse the string by the following operations

10

it means : suppose for 1st test case “abdeba”, you perform operation on ‘a’ 2 times,say O1 - one for the last indexed ‘a’ and second time for the first indexed ‘a’, then the result you get with it will be same if you perform the operation on ‘a’ only one time,say O2 - ie on the last indexed ‘a’. So O2 < O1, as 1< 2. and the resulting string is also same.

11

What is the logic behind this code bro can you explain?

12

I guess he used the same approach as in the editorial.

14

assume string is abdeba
if we selected d abebad steps =1
then b abeadb steps =2
lastly a abedba steps =3

so we can reverse it in 3 steps
that’s why n - cnt == 7 - 4 = 3.