Rotated Palindrome
December 15, 2017
Today’s exercise provides simple finger exercise for a Friday morning:
A palindrome is a string that reads the same forward and backward; for instance “abcdedcba” is a palindrome. A rotated palindrome is a string that reads the same forward and backward, either directly or in any rotation of the string; for instance, “dedcbaabc” is a rotated palindrome, because if the last three letters at the end of the string are rotated to the beginning of the string, it becomes “abcdedcba” which is a palindrome.
Your task is to write a program to determine if a string is a rotated palindrome. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
An observation: the rotation of a palindromic string is of the form B X B’ A’ A or A’ A B X B’, where A’, B’ is the reverse of A, B and any of A, B or X might be empty.
Another observation: if S’ is a substring of S S, then S must be of the form A B where A = A’ and B = B’
Here’s some code: match reverse string as above, then each part of even length can be wrapped around the other part to get a palindrome:
import sys s = sys.argv[1] ss = s+s k = 0 while True: k = ss.find(s[::-1],k) if k == -1 or k == len(s): break a = s[:k]; i = len(a) b = s[k:]; j = len(b) print(s,ss,k,a,b) if i%2 == 0: print(a[i//2:]+b+a[:i//2]) if j%2 == 0: print(b[j//2:]+a+b[:j//2]) k += 1$ rpal.py dedcbaabc ('dedcbaabc', 'dedcbaabcdedcbaabc', 3, 'ded', 'cbaabc') abcdedcba $ rpal.py deedcbaabc ('deedcbaabc', 'deedcbaabcdeedcbaabc', 4, 'deed', 'cbaabc') edcbaabcde abcdeedcbaHere’s a solution in C99.
#include <stdbool.h> #include <stdio.h> #include <string.h> bool CheckIfRotatedPalindrome(char* string) { size_t n = strlen(string); if (n == 0) return true; for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n/2; ++j) { char c1 = string[(i + j) % n]; char c2 = string[(i + n - j - 1) % n]; if (c1 != c2) goto outer; } return true; outer:; } return false; } int main(int argc, char* argv[]) { char* strings[] = {"dedcbaabc", "aba", "aab", "abc", "", "ab", "a", "aaabba", "abab"}; size_t n = sizeof(strings) / sizeof(char*); for (size_t i = 0; i < n; ++i) { char* string = strings[i]; bool is_rotated_palindrome = CheckIfRotatedPalindrome(string); printf("CheckIfRotatedPalindrome(\"%s\"): %d\n", string, is_rotated_palindrome); } return 0; }Output:
CheckIfRotatedPalindrome("dedcbaabc"): 1 CheckIfRotatedPalindrome("aba"): 1 CheckIfRotatedPalindrome("aab"): 1 CheckIfRotatedPalindrome("abc"): 0 CheckIfRotatedPalindrome(""): 1 CheckIfRotatedPalindrome("ab"): 0 CheckIfRotatedPalindrome("a"): 1 CheckIfRotatedPalindrome("aaabba"): 1 CheckIfRotatedPalindrome("abab"): 0In Python
def rotations(txt): yield txt for pos in range(1, len(txt)): txt = txt[1:] + txt[0] yield txt def is_rotated_palindrome(txt): return any(t==t[::-1] for t in rotations(txt))A Haskell version. The isPalindrome function is arguably a little too cute, but it’s a clever use of the Monad instance of lists I once saw on Reddit.
import Data.List -- All rotations of the argument. rotations :: [a] -> [[a]] rotations xs = let n = length xs in take n . map (take n) . tails . cycle $ xs -- True iff the argument is a palindrome. isPalindrome :: Eq a => [a] -> Bool isPalindrome = reverse >>= (==) -- True iff any rotation of the argument is a palindrome. isRotatedPalindrome :: Eq a => [a] -> Bool isRotatedPalindrome = any isPalindrome . rotations main :: IO () main = do print $ isRotatedPalindrome [1, 2, 3] print $ isRotatedPalindrome "dedcbaabc"My solution above can run in O(n) time, using a suitable string find algorithm such as Knuth-Morris-Pratt. I wonder if there is a way to use the KMP tables more directly to solve the problem.
One-liner in Python. It basically says is there any possible middle point of the string for which all index left/right are equal. Python support negative indexing, so no need to ‘rotate’ the string yourself.
@Rutger: neat, but seems to only work for odd-length strings.
asd
Here is the solution is
QBasicSCREEN 12 CLS PRINT "CHECKING FOR ROTATED PALINDROMES" INPUT "Enter a string: "; s$ l = LEN(s$) ans = 0 FOR y = 1 TO l new$ = MID$(s$, y + 1, l) + MID$(s$, 1, y) check$ = "" FOR x = l TO 1 STEP -1 check$ = check$ + MID$(new$, x, 1) NEXT x IF check$ = new$ THEN ans = 1 EXIT FOR END IF NEXT y PRINT: PRINT IF ans = 1 THEN PRINT "Yes, this is a ROTATED PALINDROME, as "; s$; " rotates to form "; check$; ", which is a palindrome." ELSE PRINT "No, "; s$; " is not a ROTATED PALINDROME" END IFHere is java 8 solution
public class RotatedPalindrome { public boolean isRotatablePalindrome(String input) { if (input != null) { return IntStream.range(0, input.length()).anyMatch(i -> isPalindrome(new StringBuilder(input.substring(i, input.length())).append(input.substring(0, i)).toString())); } return false; } private boolean isPalindrome(String input) { return input.equals(new StringBuilder(input).reverse().toString()); } public static void main(String[] args) { String one = "abcdedcba"; RotatedPalindrome tester = new RotatedPalindrome(); System.out.println(tester.isRotatablePalindrome(one)); String two = "dedcbaabc"; System.out.println(tester.isRotatablePalindrome(two)); } }Here’s a version of Rutger’s solution that handles the even-length case. Not quite a one-liner, but short enough. Also a little test function, comparing the new function with findpals from above:
def checkpal(s): n = len(s); k = n%2 check = lambda i: all(s[(i+j+k)%n] == s[i-j-1] for j in range(n//2)) return any(check(i) for i in range(n)) i = 1 while True: s = "{0:o}".format(i) p = findpals(s) assert(checkpal(s) == (len(findpals(s)) > 0)) i += 1Season’s greetings to all.