Game of Thrones

Online challenge on Hacker Rank.


The king has a string composed of lowercase English letters. Help him
figure out whether any anagram of the string can be a palindrome or
not.


Input Format


A single line which contains the input string.


Constraints


1 <= length of string <= 10^5


Each character of the string is a lowercase English letter.


Output Format


A single line which contains YES or NO in uppercase.

public class Solution {
        private static String hasPalindrome(String message) {
            // Observation: For even length every character should appear even number of times.
            // For odd length string there should be only one odd length character and rest even.
            Map map = new HashMap<>();
            for (Character c : message.toCharArray()) {
                int count = map.containsKey(c) ? map.get(c) + 1 : 1;
                map.put(c, count);
            }

            int numOdds  = 0;
            int numEvens = 0;
            int numChars = 0;
            for (Map.Entry entry : map.entrySet()) {
                if (entry.getValue() % 2 == 0) {
                    numEvens++;
                } else {
                    if (numOdds == 1) return "NO";
                    numOdds++;
                }
                numChars++;
            }
            if (message.length() % 2 == 0) {
                return numChars == numEvens ? "YES" : "NO";
            } else {
                return numOdds == 1 ? "YES" : "NO";
            }
        }

        public static void main(String[] args) {
            Scanner myScan = new Scanner(System.in);
            String inputString = myScan.nextLine();

            String ans = hasPalindrome(inputString);
            System.out.println(ans);
            myScan.close();
        }
    }

Write for reuse

private static String hasPalindrome(String message) {

By convention, a method named hasPalindrome or isPalindrome should return a boolean.

private static boolean hasPalindrome(String message) {

Then we need to change the returns

if (numOdds == 1) return "NO";
                    numOdds++;
                }
                numChars++;
            }
            if (message.length() % 2 == 0) {
                return numChars == numEvens ? "YES" : "NO";
            } else {
                return numOdds == 1 ? "YES" : "NO";

to

if (numOdds >= 1) {
                    return false;
                }
                numOdds++;
            }
            numChars++;
        }
        if (message.length() % 2 == 0) {
            return numChars == numEvens;
        } else {
            return numOdds == 1;

Note how this simplifies two of the returns.

I also switched a use of the single statement form of if to the block form, as I find it more robust to always use the block form.

I changed a strict equality check to a range check as better reflecting the question. We only have one middle character and thus only one character can have an odd count.

Then in

String ans = hasPalindrome(inputString);

We can say

String answer = hasPalindrome(inputString) ? "YES" : "NO";

This both makes hasPalindrome more flexible and centralizes the display. So rather than write three NOs and two YESes, we can write each only once.

I would prefer to write out answer rather than abbreviating it.

The containKeys method is not needed here

int count = map.containsKey(c) ? map.get(c) + 1 : 1;
                map.put(c, count);

Can be written

Integer count = map.get(c);
            if (count == null) {
                count = 0;
            }
            map.put(c, count + 1);

Whenever containsKey would return false, get will return null. And vice versa.

We don't need to count

int numOdds  = 0;
            int numEvens = 0;
            int numChars = 0;
            for (Map.Entry entry : map.entrySet()) {
                if (entry.getValue() % 2 == 0) {
                    numEvens++;
                } else {
                    if (numOdds == 1) return "NO";
                    numOdds++;
                }
                numChars++;
            }
            if (message.length() % 2 == 0) {
                return numChars == numEvens ? "YES" : "NO";
            } else {
                return numOdds == 1 ? "YES" : "NO";
            }

Rather than counting each character that appears in the map, we can just

int numChars = map.size();

and then the rest becomes simpler

int numOdds  = 0;
        int numChars = map.size();
        for (Map.Entry entry : map.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                if (numOdds == 1) return false;
                numOdds++;
            }
        }
        int numEvens = numChars - numOdds;
        if (message.length() % 2 == 0) {
            return numChars == numEvens;
        } else {
            return numOdds == 1;
        }

But we can simplify the last section of code.

int numEvens = numChars - numOdds;
        if (message.length() % 2 == 0) {
            return numChars == numEvens;

becomes

if (message.length() % 2 == 0) {
            return numChars == numChars - numOdds;

or (with algebra)

if (message.length() % 2 == 0) {
            return numOdds == 0;
        } else {
            return numOdds == 1;
        }

which gives us

return numOdds == message.length() % 2;

But we don't actually need to count the number of odd counts. The real question is only if there are too many characters with odd counts. If there are an even number of characters, that's at most zero. If odd, at most one. But we can test that directly.

int oddsNeeded = message.length() % 2;
        for (int count : map.values()) {
            if (count % 2 != 0) {
                if (oddsNeeded <= 0) {
                    return false;
                }

                oddsNeeded--;
            }
        }

        return oddsNeeded == 0;

We don't even need to count. If an odd length message, we need one odd count to balance things. Once we've found that odd count, we've used up the odd portion of the message and the remaining message is an even length. Either way, an even length message is balanced and can't handle odd counts.

```
// Observation: For even length strings every character should appear an even number of times.
// For odd length strings there should be only one odd length character and rest even.
Map map = new HashMap<>();
for (Character c : message.toCharArray()) {
Integer count = map.get(c);
if (count == null) {
count = 0;
}

map.put(c, count + 1);
}

b

StackExchange Code Review Q#150958, answer score: 5