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.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: