Rotated Palindrome
December 15, 2017
We begin by writing two utility functions on strings; string-reverse reverses the characters in a string, and string-rotate moves n characters from the front of a string to the back. Both functions work by converting the strings to lists of characters, then calling functions on lists to perform the conversion, finally converting the lists back to strings:
(define (string-reverse str) (list->string (reverse (string->list str))))
(define (string-rotate n str)
(call-with-values
(lambda () (split n (string->list str)))
(lambda (front back) (list->string (append back front)))))
Then it is easy to check if a string is a rotated palindrome by rotating the string one character at a time, checking each rotation to see if it is a palindrome:
(define (rot-pal? str)
(let loop ((n (string-length str)) (str str))
(if (zero? n) #f
(if (string=? str (string-reverse str)) #t
(loop (- n 1) (string-rotate 1 str))))))
You can run the program at https://ideone.com/DqWBKA.
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.