6
\$\begingroup\$

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<Character, Integer> 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<Character, Integer> 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();
        }
    }
\$\endgroup\$
5
\$\begingroup\$

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<Character, Integer> 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<Character, Integer> 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<Character, Integer> map = new HashMap<>();
        for (Character c : message.toCharArray()) {
            Integer count = map.get(c);
            if (count == null) {
                count = 0;
            }

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

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

                balanced = true;
            }
        }

        return balanced;

If the string has an even length, this allows zero characters with an odd count. If it finds one, it immediately returns false. Otherwise balanced is true and it returns true.

If the string has an odd length, this allows one character with an odd count. If it finds one, it changes balanced to true. If it finds another, it immediately returns false. If it found exactly one, balanced is true and it returns true. If it found none, balanced is false and it returns false.

Note that this also doesn't bother with entrySet. Instead, it looks at the values directly.

try-with-resources

It doesn't matter much here, but

            Scanner myScan = new Scanner(System.in);
            String inputString = myScan.nextLine();

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

could be written

        try (Scanner myScan = new Scanner(System.in)) {
            String inputString = myScan.nextLine();

            String answer = hasPalindrome(inputString);
            System.out.println(answer);
        }

The close is no longer needed, as the try-with-resources will handle it.

\$\endgroup\$
  • \$\begingroup\$ I have to agree now that solving more problems isn't helping much I still cannot get this out of the box thinking stuff like you did it with balanced flag, apart from practice what you think the mental model should be or at least some general tips would help me a lot. \$\endgroup\$ – CodeYogi Jan 8 '17 at 19:05
  • \$\begingroup\$ @CodeYogi I added more of the intermediate steps in case that helps. I didn't record them as I went, but I think that this roughly follows the original process. \$\endgroup\$ – mdfst13 Jan 9 '17 at 2:59

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.