267. Palindrome Permutation II

Reference: LeetCode
Difficulty: Medium

My Post: Java Solutions with Explanations and Comments (brute-force & backtracking)

Problem

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Example:

Input: "aabb"
Output: ["abba", "baab"]

Input: "abc"
Output: []

Hint: If a palindromic permutation exists, we just need to generate the first half of the string.

Analysis

Brute-Force

The brute-force solution is based on the same idea in 266. Palindrome Permutation I. Since we have to deal with duplicate cases, we apply the approach of using a hash set skip considered elements.

Note:

public List<String> generatePalindromes(String s) {
  List<String> result = new ArrayList<>();
  StringBuilder sb = new StringBuilder(s);
  permute(0, s.length(), sb, result);
  return result;
}

private void permute(int d, int n, StringBuilder sb, List<String> result) {
  if (d == n) {
    if (testPalindromicity(sb)) result.add(sb.toString());
    return;
  }
  
  Set<Character> testSet = new HashSet<>();
  for (int i = d; i < n; ++i) {
    char ch = sb.charAt(i);
    if (testSet.contains(ch)) continue;
    testSet.add(ch);
    swap(sb, d, i);
    permute(d + 1, n, sb, result);
    swap(sb, d, i);
  }
}

// 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 \times N!)$

Backtracking

To construct a palindrome we build the first half, append the middle character (odd case), and concatenate the reversed string of the first half.

Before the permutation, we need to know what characters we need to construct the first half, and also find out what the middle character is if it exists. It could be done in the function checkAndConstruct of counting occurrences (see the code for details).

The idea is not difficult, but the implementation is.

Note: If the count is odd and greater than $1$, this character could both lie in the first half and the middle position, e.g. "ababa".

Helper class BuildInfo:

private class BuildInfo {
  StringBuilder sb;
  String oddChar;
  BuildInfo(StringBuilder s, String o) {
    sb = s;
    oddChar = o;
  }
}

Main function:

public List<String> generatePalindromes(String s) {
  List<String> result = new ArrayList<>();
  // count
  BuildInfo info = new BuildInfo(new StringBuilder(), "");
  if (checkAndConstruct(s, info) == false) return result; // cannot form palindrome
  
  permute(0, info.sb.length(), info, result);
  
  return result;
}

Check palindromicity and construct BuildInfo for permuting.

private boolean checkAndConstruct(String s, BuildInfo info) {
  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);
  }
  if (totalCount > 1) return false;
  // construct StringBuilder sb and oddChar
  for (char ch : map.keySet()) {
    int count = map.get(ch);
    if (count % 2 == 0) { // skip the odd char
      for (int i = 0; i < count / 2; ++i) { // add the left half
        info.sb.append(ch);
      }
    } else { // meet odd count (could be "a" or "aaa" or ...)
      if (count > 1) {
        for (int i = 0; i < (count - 1) / 2; ++i) { // if count = 5, add ch for (5-1)/2 = 2 times
          info.sb.append(ch);
        }
      }
      info.oddChar = Character.toString(ch);
    }
  }
  return true;
}

Permutation:

private void permute(int d, int n, BuildInfo info, List<String> result) {
  if (d == n) { // only stops at left half
    StringBuilder reverseSb = new StringBuilder(info.sb.toString());
    reverseSb.reverse();
    result.add(info.sb.toString() + info.oddChar + reverseSb.toString());
    return;
  }
  
  Set<Character> dupTestSet = new HashSet<>();
  for (int i = d; i < n; ++i) {
    char ch = info.sb.charAt(i);
    if (dupTestSet.contains(ch)) continue;
    dupTestSet.add(ch);
    swap(info.sb, d, i);
    permute(d + 1, n, info, result);
    swap(info.sb, d, i);
  }
}

// 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);
}

Time: $O(N \times \frac{N}{2}!)$
Space: $O(N \times \frac{N}{2}!)$