saket9450's blog

cyclic palindrome problem
By saket9450, history, 10 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

Comments Comments (5)
| Write comment?
»
10 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.

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

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

    → Reply
    • »
      »
      »
      10 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.

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

      hashes, Manacher's algorithm or palindromic tree

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

    thanks for help tenshi_kanade i got it :D .

    → Reply