# Check if a given string is a rotation of a palindrome

StringViews 1605

## Given a string, write a function that will return TRUE if it is a rotation of any palindrom else return FALSE

### Example 1

INPUT :
s = “cbbcd”

OUTPUT :
TRUE

In the above example, the given string “cbbcd” is a rotation of a palindrom “bcdcb”

### Example 2

INPUT :
s = “aac”

OUTPUT :
TRUE

In the above example, the given string “aac” is a rotation of a palindrom “aca”

Time Complexity : O(n^2)

Space Complexity : O(n) for storing rotations

In this method the main idea is to rotate the string in every possible way, if any rotation is a palindrome then return TRUE

## Algorithm

1. Check every rotation in the given string is a palindrome

Till the length of the given string

a. Divide the given string into two halves such that, s1 = s[0..i+1] and s2 = s[i+1….n-i+1]
b. Append s2 with s1
c. Check whether the appended string is a palindrome

Implementation of above algorithm for string “abcd”
s = “abcd”
First check whether the given string s is a palindrome or not, it is not
Divide the string
s1 = “a”, s2 = “bcd”
Append s2.s1 = “bcda” which is not a palindrome
Again, divide the string
s1 = “ab”, s2 = “cd”
Append s2.s1 = “cdab” which is not a palindrome
Again, divide the string
s1 = “abc”, s2 = “d”
Append s2.s1 = “dabc” which is not a palindrome

## C++ Program

```#include<iostream>
#include<string>
using namespace std;

//Return True if the given string is a palindrome
bool isPalindrome(string s)
{
// Start from leftmost and rightmost corners of s
int l = 0;
int h = s.length() - 1;

// Keep comparing characters while they are same
while (h > l)
if (s[l++] != s[h--])
return false;

// If all characters are matching
return true;
}

// Returns TRUE if the given string is rotation of any palindrome
bool isRotationOfPalindrome(string s)
{
// If string iteself is palindrome
if (isPalindrome(s))
return true;

//find every rotation
int n = s.length();
for (int i = 0; i < n-1; i++)
{
string s2 = s.substr(i+1, n-i-1);
string s1 = s.substr(0, i+1);
// Check if this rotation is palindrome
if (isPalindrome(s2.append(s1)))
return true;
}
return false;
}

int main()
{
string s = "cbbcd";
if(isRotationOfPalindrome(s))
{
cout<<"TRUE"<<endl;
}
else
{
cout<<"FALSE"<<endl;
}
return 0;
}```

Translate »