266. Palindrome Permutation I

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:

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.

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.

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:

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.

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)$