[LintCode] Problem 916 - Palindrome Permutation

Posted on | In ,

Given a string, determine if a permutation of the string could form a palindrome.

Example

No.1

Input: s = “code”

Output: False

Explanation:
No solution

No.2

Input: s = “aab”

Output: True

Explanation:
“aab” –> “aba”

No.3

Input: s = “carerac”

Output: True

Explanation:
“carerac” –> “carerac”

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean canPermutePalindrome(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int count = 0;

    for (Character ch : s.toCharArray())
        map.put(ch, map.getOrDefault(ch, 0) + 1);

    for (int i : map.values()) {
        if (i % 2 != 0)
            count++;

        if (count > 1)
            return false;
    }

    return true;
}