Check if a given string is a rotation of a palindrome


StringViews 3384

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;
}

Try It

 

Translate »