JavaScript Program to Check if a Given String is a Rotation of a Palindrome
In this article, we will see how to check a given string is a rotation of a palindrome. A palindrome is a string that remains the same when its characters are reversed (e.g., “racecar” is a palindrome).
Example:
Input: str = "racecar"
Output: true
// "racecar" is a rotation of a palindrome "racecar"
Input: str = "abbab"
Output: true
// "abbab" is a rotation of "abbba".
Input: str = "baba"
Output: true
// "baba" is a rotation of a palindrome "baba".
Input: str = "abcd"
Output: false
// "abcd" is not a rotation of any palimdrome.
Table of Content
- Naive Approach
- Efficient Approach:
- Using Hashing
Naive Approach
In this approach, we generate all possible rotations of the string and check if any of them is a palindrome. It does this by generating all possible rotations of the string and checking if any of these rotations are palindromes using the isPalindrome function. If it finds a palindrome rotation, it returns true; otherwise, it returns false.
Example: Below is the implementation of the above example.
function isPalindrome(str) {
const len = str.length;
for (let i = 0; i < len / 2; i++) {
if (str[i] !== str[len - 1 - i]) {
return false;
}
}
return true;
}
function isRotationOfPalindrome(str) {
if (!str || str.length <= 1) {
return false;
}
const len = str.length;
// Generate all possible rotations
for (let i = 0; i < len; i++) {
const rotated =
str.slice(i) + str.slice(0, i);
// Check if the original string is a palindrome
if (isPalindrome(rotated)) {
return true;
}
}
return false;
}
const inputString = "abcd";
const isRotatedPalindrome =
isRotationOfPalindrome(inputString);
console.log(isRotatedPalindrome);
Output
false
Time Complexity: O(N^2), where N is the length of the input string
Auxiliary Space: O(N)
Efficient Approach:
In this approach, we will find a specific rotation that makes it easier to determine if the string is a rotation of a palindrome. The code checks if a given string is a rotation of a palindrome. It creates a doubled version of the input string to handle all possible rotations efficiently. Then, it iterates through the doubled string, extracting substrings of the same length as the original string and checking if any of these substrings are palindromes using the isPalindrome function. If it finds a palindrome rotation, it returns true, otherwise, it returns false.
Example: Below is the implementation of the above example.
function isRotationOfPalindrome(str) {
if (!str || str.length <= 1) {
return false;
}
const len = str.length;
// Create a doubled string to handle
// all rotations
const doubledStr = str + str;
// Iterate through the string length
for (let i = 0; i < len; i++) {
const possibleRotation =
doubledStr.slice(i, i + len);
// Check if the possible
// rotation is a palindrome
if (isPalindrome(possibleRotation)) {
return true;
}
}
return false;
}
function isPalindrome(str) {
const len = str.length;
for (let i = 0; i < len / 2; i++) {
if (str[i] !== str[len - 1 - i]) {
return false;
}
}
return true;
}
const inputString = 'abba';
const isRotatedPalindrome =
isRotationOfPalindrome(inputString);
console.log(isRotatedPalindrome);
Output
true
Time Complexity: O(N), where N is the length of the input string
Auxiliary Space: O(N)
Using Hashing
Using hashing, the approach compares the original string’s hash with the hashes of all its rotations. If any rotation’s hash matches, it verifies if the substring is a palindrome, determining if the string is a rotation of a palindrome.
Example:
function isRotationOfPalindrome(str) {
function isPalindrome(s) {
return s === s.split('').reverse().join('');
}
function computeHash(s) {
let hash = 0;
for (let i = 0; i < s.length; i++) {
hash = (hash * 31 + s.charCodeAt(i)) % (1e9 + 7);
}
return hash;
}
let originalHash = computeHash(str);
let n = str.length;
let power = 1;
let currentHash = 0;
for (let i = 0; i < n; i++) {
currentHash = (currentHash * 31 + str.charCodeAt(i)) % (1e9 + 7);
if (i < n - 1) {
power = (power * 31) % (1e9 + 7);
}
}
for (let i = 0; i < n; i++) {
if (currentHash === originalHash && isPalindrome(str.slice(i) + str.slice(0, i))) {
return true;
}
currentHash = (currentHash - (str.charCodeAt(i) * power) % (1e9 + 7) + (1e9 + 7)) % (1e9 + 7);
currentHash = (currentHash * 31 + str.charCodeAt((i + n) % n)) % (1e9 + 7);
}
return false;
}
console.log(isRotationOfPalindrome("abcd")); // false
console.log(isRotationOfPalindrome("aab")); // true
Output
false false
Using Character Frequency Count
In this approach, we’ll determine if the given string can be rearranged into a palindrome. If it can, then it must be a rotation of some palindrome. This is based on the fact that a string that can be rearranged into a palindrome must have at most one character with an odd frequency.
Example:
function canFormPalindrome(str) {
const charCount = new Map();
// Count the frequency of each character
for (let char of str) {
if (charCount.has(char)) {
charCount.set(char, charCount.get(char) + 1);
} else {
charCount.set(char, 1);
}
}
// Check the number of characters with odd frequency
let oddCount = 0;
for (let count of charCount.values()) {
if (count % 2 !== 0) {
oddCount++;
}
}
// For a string to be rearranged into a palindrome,
// there can be at most one character with an odd frequency
return oddCount <= 1;
}
function isRotationOfPalindrome(str) {
// If the string can form a palindrome, then
// it must be a rotation of some palindrome
return canFormPalindrome(str);
}
// Test cases
console.log(isRotationOfPalindrome("racecar"));
console.log(isRotationOfPalindrome("abbab"));
console.log(isRotationOfPalindrome("baba"));
console.log(isRotationOfPalindrome("abcd"));
console.log(isRotationOfPalindrome("aab"));
Output
true true true false true