palindrome permutation

This is a leetcode problem.

Write an efficient function that checks whether any permutation of an input string is a palindrome. Examples:
 "civic" should return true
 "ivicc" should return true
 "civil" should return false
 "livci" should return false

In a palindrome string, all characters appears symmetrically, except the middle character if the string length is odd. The key observation is that to count the appearances of each characters in the string, if all counts are even, or there is only one characters appears odd times, then the word is palindrome. And we use an array to store the counts for each character in the string. This kind of simple counting array is more space effective than using hash map to store character and its count. Here is the code.

	// Leetcode: Palindrome Permutation
	public static boolean hasPaliPermu(String s){
	int[] apps = new int[256];
	for(int i=0; i<s.length(); i++){
	char c = s.charAt(i);
	apps[c] = (apps[c]+1)%2;
	}
	int count = 0;
	for(int i=0;i<256;i++){
	if(apps[i] == 1)
	count++;
	}
	return count<2;
	}

view raw palindromePermutation.java hosted with ❤ by GitHub