Sharing my O(n) JAVA solution with explanation !


  • 0
    C
    public boolean canPermutePalindrome(String s) {
            
            Map<Character, Integer> counts = new HashMap<>();
            int odds = 0;
            // Create a mapping of characters versus occurrence count in string
            for (char c : s.toCharArray()) {
                if (!counts.containsKey(c)) {
                    counts.put(c, 0);
                }
                counts.put(c, counts.get(c) + 1);
            }
            
            // A palindrome of even length has all characters of an even count
            // A palindrome of odd length has only 1 character (middle) of odd count = 1
            for (int count : counts.values()) {
                if (count % 2 > 0) {
                    if (++odds > 1) return false;
                }
            }
            return true;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.