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.

Advertisements

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[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
    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[0]
            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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: