Created
June 10, 2014 10:50
-
-
Save Sefford/44635449b01f9e22f910 to your computer and use it in GitHub Desktop.
A solution to the problem to find if a String is an anagram of a Palindrome
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// In order to know if a String or char[] is an anagram of a palindrome we look up to the | |
// math definition of a palindrome: There must be an even number of every char except for the | |
// case there is a single letter in the middle, in which case we can afford only 1 instance of | |
// an odd character in the middle. | |
public boolean solution(char[] input) { | |
int[] letters = new int[26]; | |
// We calculate frequencies to each of the letters | |
for (int i = 0; i < input.length; i++) { | |
// We lowercase the chars and compensate for the UTF-8 displacement to the right | |
letters[Character.getNumericValue(Character.toLowerCase(input[i])) - 10]++; | |
} | |
// Counting odd characters. | |
int oddCounter = 0; | |
for (int i = 0; i < letters.length; i++) { | |
if (letters[i] % 2 != 0) { | |
oddCounter++; | |
} | |
} | |
// O(n+26) still accounts for O(n) :P | |
return oddCounter <= 1; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment