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));
            }
    }

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.