Reference: LeetCode
Difficulty: Easy

My Post: Java B-F, HashTable Solutions with Comments and Explanation (easy-understand)

Problem

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

Example:

1
2
3
4
5
6
7
8
Input: "code"
Output: false

Input: "aab"
Output: true

Input: "carerac"
Output: true

Follow up:

Analysis

Brute-Force

List all possibilities and test if they satisfy palindromicity.

Note: Swapping characters in string can be done with StringBuilder.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public boolean canPermutePalindrome(String s) {
StringBuilder sb = new StringBuilder(s);
return permute(0, s.length(), sb);
}

private boolean permute(int d, int n, StringBuilder sb) {
if (d == n) {
return testPalindromicity(sb);
}

for (int i = d; i < n; ++i) {
swap(sb, d, i);
if (permute(d + 1, n, sb)) return true;
swap(sb, d, i);
}
return false;
}

// swap characters in a StringBuilder
private void swap(StringBuilder sb, int i, int j) {
char temp = sb.charAt(i);
sb.setCharAt(i, sb.charAt(j));
sb.setCharAt(j, temp);
}

private boolean testPalindromicity(StringBuilder sb) {
int n = sb.length();
for (int i = 0; i < n / 2; ++i) {
if (sb.charAt(i) != sb.charAt(n - i - 1)) return false;
}
return true;
}

Time: $O(N \times N!)$
Space: $O(N)$

Hash Map

We can use hash map based on the fact that odd number of occurrences of a specific character can only occur once at most.

Actually, since there are only 128 ASCII characters, we can use an array of size 128 to store occurrences.

Note: But I think the code is not elegant.

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<>();
// count
for (char ch : s.toCharArray()) {
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
// check
boolean hasMetOdd = false;
for (char ch : map.keySet()) {
int count = map.get(ch);
if (count % 2 != 0) { // meet odd
if (hasMetOdd) return false;
hasMetOdd = true;
}
}
return true;
}

A more elegant version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean canPermutePalindrome(String s) {
Map<Character, Integer> map = new HashMap<>();
// count
for (char ch : s.toCharArray()) {
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
// check
int totalCount = 0;
for (char ch : map.keySet()) {
int count = map.get(ch);
totalCount += (count % 2); // do not add odd count
} /* if odd count occurs more than once, totalCount would be > 1 */
return count <= 1;
}

Time: $O(N)$
Space: $O(N)$

Hash Set

Idea: Only character with odd number of occurrences will be in the hash set.

1
2
3
4
5
6
7
8
9
10
public boolean canPermutePalindrome(String s) {
Set<Character> set = new HashSet<>();
// count
for (char ch : s.toCharArray()) {
if (set.contains(ch)) set.remove(ch);
else set.add(ch);
}
// check
return set.size() <= 1;
}

Time: $O(N)$
Space: $O(N)$


Comment