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;
}