Skip to content

Instantly share code, notes, and snippets.

@Sefford
Created June 10, 2014 10:50
Show Gist options
  • Save Sefford/44635449b01f9e22f910 to your computer and use it in GitHub Desktop.
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
// 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