Determining whether a string can be rearranged into a palindrome

Question

For a string, count the number of occurences of each character. If at most one character has odd count then the string can be a palindrome else it's not.

public class Palindrome {
 //count the chars in the input string
 //if not more than one character has odd count then palindrome is possible
 public static boolean isPalindromPossible(String input)
 {
 int[] charCount = new int[128];
 for(int i = 0 ; i < input.length() ; i++)
 {
 charCount[(int)input.charAt(i)]++;
 }
 int oddCount = 0 ;
 for(int i = 0 ; i < 128 ; i++)
 {
 if(charCount[i] % 2!=0)
 {
 oddCount++;
 }
 }
 if(oddCount != 0 && oddCount != 1)
 {
 return false;
 }
 return true;
 }
 public static void main(String[] args) {
 String input = "aacaacc";
 System.out.println(isPalindromPossible(input));
 }
 }

• pacmaninbw: What would happen with abba?
• saneGuy: returns true as there is not character with odd count
• Zack: Determining if the string is really a palindrome is actually less work than counting oddness of letters to determine if it might be a palindrome.
• Zack: @saneGuy return (input.equals(new StringBuilder(input).reverse().toString() ? true : false)
• I'll add comments tomorrow: @Zack this is not the question being asked.

Answer 1

• int

  All the counters are inherently non-negative. I recommend to make them unsigned, just to clarify your intentions.

• What to return

  • Computing return value

     if (condition) {
     return false;
     }
     return true;
    

    is a long way to say

     return !condition;
    

  • Actual condition

     oddCount != 0 && oddCount != 1
    

  is a long way to say

   oddCount > 1
  

  So I recommend to simply

   return oddCount < 2; 
  

• Efficiency

  I wouldn't bother about performance at all. However, you may shave few cycles:

   ....
   charCount[(int)input.charAt(i)] ^= 1;
   ....
   oddCount += charCount[i];
  

  thus avoiding taking modulo and making decisions inside the loop. I don't think it will make any difference however.

• Assumptions and restrictions

  Traditionally A man, a plan, a canal, Panama! is considered a palindrome. You really need to say what is a palindrome in your setting.

• 200_success: There are no unsigned ints in Java.
• vnp: @200_success What a shame.