## 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.

Pages: 1 2

### 12 Responses to “Rotated Palindrome”

1. matthew said

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’

2. matthew said

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
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
abcdeedcba
```
3. Daniel said

Here’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"): 0
```
4. Paul said

In Python

```def rotations(txt):
yield txt
for pos in range(1, len(txt)):
txt = txt[1:] + txt
yield txt

def is_rotated_palindrome(txt):
return any(t==t[::-1] for t in rotations(txt))
```
5. Globules said

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"
```
```\$ ./rotpal
False
True
```
6. matthew said

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.

7. Rutger said

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.

```def is_rotated_palindrome(s):
return any([all(s[(mid_index+i)%len(s)] == s[mid_index-i] for i in range(len(s)//2+1)) for mid_index in range(0, len(s))])

test_cases = ['2332101', 'dedcbaabc', '12321', 'dedcbaabd']

for t in test_cases:
print(t, is_rotated_palindrome(t))

# output:
# 2332101 True
# dedcbaabc True
# 12321 True
# dedcbaabd False
```
8. matthew said

@Rutger: neat, but seems to only work for odd-length strings.

9. Mrigank Pawagi said

asd

10. Mrigank Pawagi said

Here is the solution is `QBasic`

```SCREEN 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 IF
```
11. vinoth m said

Here 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));
}
}
```
12. matthew said

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 += 1
```

Season’s greetings to all.