### saket9450's blog

By saket9450, history, 5 years ago, , hacker rank problem can any one please give me some hint to solve this problem Comments (8)
 » 5 years ago, # | ← Rev. 2 →   If the input is small enough (constraints aren't specified), you can just append another copy of S to the back of it and check all substrings of length |S|. If you find a palindrome at position i (counting from 0), then the required number of shifts is min(|S| - i, i). Output the minimum among all of them.
•  » » Check every substring of length |S| .....by what ....using hash?
•  » » » I am not sure at all but I think he is talking about KMP algorithm.
•  » » » No, character by character with one pointer from each end. It'd be costly, that's why I said if constraints are small enough. I'd need to try to be sure, since they aren't specified in the problem statement.
•  » » » » Can't it be solved using KMP ?
•  » » » hashes, Manacher's algorithm or palindromic tree
•  » » thanks for help tenshi_kanade i got it :D .
»

# include<bits/stdc++.h>

using namespace std;

bool ispali(string s){ for(int i=0,j=s.size()-1;i<j;i++,j--) if(s[i]!=s[j]) return false; return true; }

void rotateFront(string& str){

string s=str;

for(int j=0;j<str.size();j++){
s[j]=str[(j+1)%str.size()];
}

str=s;
//cout<<"A-"<<str<<endl;

}

void rotateBack(string& str){ string s=str;

s=str[str.size()-1];

for(int j=str.size()-1;j>0;j--){
s[j]=str[j-1];
}

str=s;
//cout<<"B-"<<str<<endl;

}

int main() { int T; cin>>T; while(T--){ int res=-1; string str,s1,s2; cin>>str;

if(ispali(str)){
cout<<0<<endl;
}
else{
s1=s2=str;

for(int it=0;it<str.size();it++){
rotateFront(s1);
rotateBack(s2);
if(ispali(s1) or ispali(s2)){
res=it+1;
break;
}
}

cout<<res<<endl;
}
}
return 0;

}