Solutions: Testing an Anagram of a Palindrome

There are many solutions to this problem. However, it is made simpler if you determine the number of letter with an odd number occurrences. As long as the text has no more than 1 odd numbered letter, you can make a palindrome from it.

A straight forward solution

public static boolean isPalindromeAnagram(String text) {
    BitSet bs = new BitSet(27);
    for (int i = 0; i < text.length(); i++) {
        char ch = text.charAt(i);
        if (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z'))
            bs.flip(ch % 32);
    }
    return bs.cardinality() <= 1;
}

A trickier solution

public static boolean isPalindromeAnagram(String text) {
    int count = 0;
    for (int i = 0; i < text.length(); i++) {
        char ch = text.charAt(i);
        if (ch + Integer.MIN_VALUE - 'A' <= 'z' + Integer.MIN_VALUE - 'A')
            count ^= 1 << ch;
    }
    return Integer.bitCount(count % (1 << 'z') & ~1) <= 1;
}

Comments

  1. This test isn't valid.
    For example "AAAABBBB" also returns true.
    Because position of characters is also important,
    not only the number of bits.

    ReplyDelete
  2. For a palindrome, position is important. For an anagram, position is not important. The palindrome "ABABBABA" is an anagram of "AAAABBBB" so both Strings should return true.

    ReplyDelete
  3. Thanks for clarification.
    Typical issue of not reading the problem definition correctly ;-)

    ReplyDelete
  4. Peter, I'm really learning Java from your blogs. Thank you and keep posting :)

    But, I've to confess that I'm still not comfortable with binary operations. Do you have any suggestion/pointers for same, what to read ?

    ReplyDelete
  5. I would suggest you experiment. Try playing with &, |, ^, <<, >>, >>> with different values. Print the numbers before and after in binary and see if you explain what happens.

    ReplyDelete

Post a Comment

Popular posts from this blog

Low Latency Microservices, A Retrospective

Unusual Java: StackTrace Extends Throwable

System wide unique nanosecond timestamps