Check if a string is rotated palindrome or not

Given a string, check if it is a rotated palindrome or not.

 

For example,

 

CBAABCD is a rotated palindrome as it is rotation of palindrome ABCDCBA
BAABCC is a rotated palindrome as it is rotation of palindrome ABCCBA

 
Naive solution would be to consider all rotations of the given string and check if any rotation is a palindrome or not. If we have found a rotation that is a palindrome, we return true else we return false.

 
Below is C++ implementation of the idea –

 

Download   Run Code

Output:

Yes

 

Approach 2:

The problem is similar to finding Longest Palindromic Substring problem. Let the given string be S of length m. The idea is to concatenate the given string with itself i.e (S = S + S) and find palindromic substring of length m in the modified string (S + S). If palindromic substring of length m exists in the modified string, we return true else we return false.

 
Below is C++ and Java implementation of the idea –

C++

Download   Run Code

Java

Download   Run Code

Output:

Yes

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
tom
Guest

in solution 2, line 31, shouldn’t we be able to use only one expand depending on whether k is odd or even? i.e. expand(str, i, i, k) if k % 2 else expand(str, i, i+1, k); Otherwise if k is even, expand(str, i, i, k) still always gets called without ever going to find a solution.

arandomguy
Guest

I agree too. Also in line 28, ‘i’ should start from ‘(k-1)/2’ and not 0, as ‘str[i]’ is the mid-point.

TusharS
Guest

Python3