saket9450's blog

By saket9450, history, 4 years ago, In English,

hacker rank problem can any one please give me some hint to solve this problem

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check every substring of length |S| .....by what ....using hash?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not sure at all but I think he is talking about KMP algorithm.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hashes, Manacher's algorithm or palindromic tree

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    thanks for help tenshi_kanade i got it :D .

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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[0]=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;

}