0
\$\begingroup\$

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));
            }
    }
\$\endgroup\$
11
  • \$\begingroup\$ What would happen with abba? \$\endgroup\$
    – pacmaninbw
    Apr 22, 2016 at 16:41
  • \$\begingroup\$ returns true as there is not character with odd count \$\endgroup\$
    – saneGuy
    Apr 22, 2016 at 16:43
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Zack
    Apr 22, 2016 at 18:25
  • \$\begingroup\$ @saneGuy return (input.equals(new StringBuilder(input).reverse().toString() ? true : false); \$\endgroup\$
    – Zack
    Apr 22, 2016 at 18:34
  • \$\begingroup\$ @Zack this is not the question being asked. \$\endgroup\$ Apr 22, 2016 at 18:35

1 Answer 1

5
\$\begingroup\$
  • 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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ There are no unsigned ints in Java. \$\endgroup\$ Apr 24, 2016 at 2:39
  • \$\begingroup\$ @200_success What a shame. \$\endgroup\$
    – vnp
    Apr 25, 2016 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.