PROBLEM LINK:
Practice
Contest
Author: Ritesh Gupta
Tester: Sachin Yadav
Editorialist: Ritesh Gupta
DIFFICULTY:
SIMPLE
PREREQUISITES:
AD-HOC, OBSERVATION
PROBLEM:
You are given a string S (1 \le |S| \le 10^6) and you have to find out whether there exists a string V of the same length such that both one left shift and one right shift on the string V produces the same string S.
QUICK EXPLANATION:
- If there are some valid V existed then one of them should be equal to the resultant string R, produced by applying the one left shift over S. Now, if one left shift and one right shift over R is equal then answer is "YES" otherwise "NO".
EXPLANATION:
OBSERVATION:
- If all character is equal in the given string then the answer should be "YES".
- In the case of two distinct characters, the given string should have them alternatively and has an even length.
- If there are more than two distinct characters in the given string then the answer is "NO".
We can say that the frequency of each character in the string V should be the same as string S because one left shift over V is equal to S and we know that by shift operation the frequency of any character in a string is not changed.
As both one left shift and one right shift on the string V produces the same string S implies that both one left shift and one right shift on the string V also be the same. It directly connects the all odd indexed characters and all even indexed characters. It is only possible when:
- if |V| \space \% \space 2 = 0 then all the odd index characters should be equal and all the even index characters should be equal.
- if |V| \space \% \space 2 = 1 then all the characters should be equal.
So, we can get that one left or one right shift over S is going to be V.
Mathematical Proof
We want a V, such that:
- LeftShift(V) is equal to S
- RightShift(V) is equal to S
1^{st} point is equivalent to saying RightShift(S) is equal to V. So, replacing V in 2^{nd} point, we get: RightShift(RightShift(S)) is equal to S which can further transform into RightShift(S) is equal to LeftShift(S).
COMPLEXITY:
TIME: O(N)
SPACE: O(N)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int cnt[30] = {0};
string s;
cin >> s;
int n = s.size();
for(auto i:s)
cnt[i-'a']++;
int count = 0;
for(int i:cnt) if(i) count++;
bool flag = true;
for(int i=1;i<s.size();i++)
{
if(s[i] == s[i-1])
{
flag = false;
break;
}
}
if(count == 1 || (count == 2 && n%2 == 0 && flag))
cout << "YES\n";
else
cout << "NO\n";
}
}
Tester's Solution
#include<iostream>
using namespace std;
typedef long long ll;
ll T, N;
string S;
int main()
{
cin>>T;
while(T--)
{
cin>>S;
N=S.length();
cout<<((S.substr(1) + S[0]) == (S[N-1] + S.substr(0,N-1))?"YES\n":"NO\n");
}
return 0;
}
7 Likes
can u give me an example of a string whose size is greater than 2 and consists of more than 1 distinct characters and L(V) == R(V).
2 Likes
#include
#include
#include
#include <bits/stdc++.h>
#include <stdio.h>
#include
using namespace std;
string strunga(){
string strungs;
cin>> strungs;
if(strungs.length()==1) return "YES";
vector<int> strung;
strung.push_back(strungs[0]);
if(strungs[1] != strungs[0]) strung.push_back(strungs[1]);
for(long i = 0 ; i< strungs.length() ; i++){
/*if(find(strung.begin(), strung.end(), strungs[i]) !=strung.end()){*/
if(strung.size() ==2)
{
if(i%2==0)
{if(strungs.length()%3==0) return "NO";
else if(strung[0] == strungs[i]) continue;
else return "NO";
}
else{
if(strung[1] == strungs[i]) continue;
else return "NO";
}
}
else
{
if(strung[0] == strungs[i]) continue;
else return "NO";
}
}
return "YES";
}
int main(){
int j;
cin>> j;
while(j!=0){
cout<<strunga()<<endl;
j–;}
return 0;
}
can anyone tell me why it is not working
Can anyone please tell why this solution is giving WA!!! I am stuck since more than an hour!
@rishup_nitdgp I applied the same logic as given in the editorial’s last 2 points.
If length is odd, all characters should be same else alternate characters should be same.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
ll t;
cin>>t;
while(t–)
{
string s;
cin>>s;
ll n=s.size(),ans=1,odd=0;
if(n%2==1)
odd=1;
for(ll i=2;i<n;i++)
{
if(odd && (s[i]!=s[i-1]) )
{
ans=0;
break;
}
else if( (!odd) && (s[i]!=s[i-2]) )
{
ans=0;
break;
}
}
if(ans)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
return 0;
}
for odd u didn’t compare s[0] with anyone…
1 Like
I can’t figure out the bug in this code yet this is tested wrong.
#include
#include
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{string s;
cin>>s;
int n=s.size();
if(n<=2){cout<<“YES”<<endl;break;}
else if(n%2==1)
{bool flag=true;
for(int i=1;i<n;i++)
{if(s[i]!=s[i-1]){flag=false;break;}}
if(flag)cout<<“YES”<<endl;
else cout<<“NO”<<endl;}
else {bool flag=true;
for(int i=2;i<n;i++)
{if(s[i]!=s[i-2]){flag=false;break;}}
if(flag)cout<<“YES”<<endl;
else cout<<“NO”<<endl;}}
return 0;
}
@anshumanprasad bro you are putting break in the if(n<=2) condition which will break out of while loop of test case. So just remove the break statement and you are good to go 
1 Like
@shivamsaluja20 It works…Thanks bro 
1 Like
Can some one please help me with my code, I had tried to create some test cases for this problem and ans that I got is same as calculated. But tested wrong!!!
https://www.codechef.com/viewsolution/32371975
I’m getting WA for this (during contest)–
https://www.codechef.com/viewsolution/32347280
Getting AC for the same code with sys.stdin.readline removed (after contest)—
https://www.codechef.com/viewsolution/32370012
Why so? Is it because of ill-formatted strings with newlines in test cases?
#include
using namespace std;
string leftshift(string st) {
string f=st;
for(int i=1;i<st.size();i++){
st[i-1]=st[i];
}
st[st.size()-1]=f[0];
return st;
}
string rightshift(string w) {
string g=w;
for(int i=0;i<w. size()-1;i++){
w[i+1]=w[i];
}
w[0]=g[g. size()-1];
return w;
}
int main() {
int a;
string s,os,l, r, ll,rr, lr,rl,k;
cin>>a;
for(int i=0;i<a; i++){
cin>>s;
os=s;
l=leftshift(s);
k=os;
r=rightshift(k);
ll=leftshift(l);
rl=rightshift(l);
s=os;
k=os;
lr=leftshift®;
rr=rightshift®;
if(os==lr&&os==rr)
cout<<“YES”<<endl;
else if(os==ll&&os==rl)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
return 0;
}
Can any one please find out why it is giving wrong answer…
1 Like
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
typedef long long int ll;
string L(string S)
{
vector<char>k;
string temp;
char y=S[0];
temp+=y;
for(int i=1;i<S.length();i++)
{
k.push_back(S[i]);
}
// S[0]=y;
// S=S+y;
// cout<<y;
for(int i=0;i<k.size();i++)
{
temp+=k[i];
}
// cout<<temp<<endl;
return temp;
}
string R(string S)
{
vector<char>k;
string temp;
char y=S[S.length()-1];
for(int i=0;i<S.length()-1;i++)
{
k.push_back(S[i]);
}
// S[0]=y;
// S=S+y;
temp+=y;
// cout<<y;
for(int i=0;i<k.size();i++)
{
temp+=k[i];
}
// cout<<temp<<endl;
return temp;
}
int main() {
fastIO;
ll T;
cin>>T;
while(T--)
{
string S,V,X;
cin>>S;
V=S;
// cout<<L(V)<<R(V)<<endl;
// cout<<L(V).length()<<R(V).length()<<endl;
if(S.length()==1||S.length()==2||(L(V)==R(V)))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
// cout<<endl;
}
return 0;
}
Whats wrong with this code guys?
HI @narendrago in your L function you are returning temp that has local scope to the function only
so if you will return something which has a local scope so it will create some problem
In addition to the solution provided (in C++) in the editorial, the python based solution is as follows:
def check_string_exist(data_string):
string_len = len(data_string)
if string_len == 1 or string_len == 2 or all(data_string[0] == c for c in data_string):
return True
is_exist = False
if not string_len % 2:
if all(data_string[0] == c for c in data_string[: : 2]) and all(data_string[1] == c for c in data_string[1: : 2]):
is_exist = True
return is_exist
def main():
for test in range(int(input().strip())):
print(f'{"YES" if check_string_exist(input().strip()) else "NO"}')
if __name__ == "__main__":
main()
For test-cases, go here: Competitive-Programming/Code-Chef/Chef-and-String at master · strikersps/Competitive-Programming · GitHub
#include
#include<string.h>
using namespace std;
int main()
{
int t,i;
cin>>t;
for(i=0;i<t;i++)
{
string s,r,l,v;
int l1,j,x,flag=0;
cin>>s;
l1=s.length();
if(l1==1)
{
cout<<"YES\n";
}
else
{
for(j=0;j<l1;j++)
{
for(x=0;x<l1;x++)
{
if(s[j]!=s[x])
{
flag=1;
break;
}
}
}
if(flag==0)
{
cout<<"YES\n";
}
else
if(l1%2==0)
{
for(j=0;j<l1/2;j++)
{
if(s[j]!=s[j+2])
{
flag=0;
}
}
if(flag==1)
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
}
}
else
{
cout<<"NO\n";
}}
}
return 0;
}
pls help…idk what im missing here?
// Whats wrong in the code ! thanks
import java.util.;
import java.lang.;
class Rep
{
public static void main(String args[])
{
LinkedList<Character> Left = new LinkedList<>();
LinkedList<Character> Right = new LinkedList<>();
LinkedList<String> value = new LinkedList<>();
String s ;
int loopnumber ;
Scanner s1 = new Scanner (System.in);
// Entering the string
// s = s1.next();
String s2="";
loopnumber = s1.nextInt();
while(loopnumber > 0)
{
s = s1.next();
for(int i=0;i<s.length()-1;i++)
{
Left.add(s.charAt(i));
}
// for converting this string into the left size //
//char c = s.charAt(n-1);
Left.add(0,s.charAt(s.length()-1));
//System.out.println(Left);
for(int i=0;i<s.length()-1;i++)
{
Right.add(s.charAt(i+1));
}
int n = Right.size();
Right.add(n,s.charAt(0));
//System.out.println(Right);
if(Left.equals(Right))
{
s2 = "YES";
}
else
{
s2 = "NO";
}
value.add(s2);
Right.clear();
Left.clear();
loopnumber-- ;
}
System.out.print(value);
}
}
#include <stdio.h>
#include<string.h>
int main(void) {
// your code goes here
int t,n,i,j,c=0;
scanf("%d",&t);
char s[1000000],v1[1000000],v2[1000000];
for(i=0;i<t;i++)
{
scanf("%s",&s);
n=strlen(s);
v2[n-1]=s[0];
v1[0]=s[n-1];
for(j=1;j<n;j++)
{
v1[j]=s[j-1];
v2[j-1]=s[j];
}
for(j=0;j<n;j++)
{
if(v1[j]!=v2[j])
{c++;
break;}
}
if(c==0)
printf(“YES\n”);
else
printf(“NO\n”);
}
return 0;
}
This shows wrong answer but when i checked with custom inputs, I got right answers. can some one explain why?
@humpty_dumpty2 You forgot to update the value c. It should be set to zero in each test case.
P.S: Always, try to attach the link to the solution instead of posting that itself.
Thank you for pointing it out! 
