Palindrome Permutation II

medium backtracking string hash map

Problem

Given a string, return all the palindromic permutations of it; an empty list if none.

Inputs = "aabb"

Output["abba","baab"]

Half multiset {a,b}. Permutations: ab → abba, ba → baab.

def generate_palindromes(s):
    from collections import Counter
    c = Counter(s)
    odd = [k for k, v in c.items() if v % 2]
    if len(odd) > 1: return []
    mid = odd[0] if odd else ""
    half = []
    for k, v in c.items():
        half.extend([k] * (v // 2))
    res = []
    seen = set()
    def back(path, avail):
        if not avail:
            p = "".join(path)
            res.append(p + mid + p[::-1])
            return
        for i in range(len(avail)):
            if i and avail[i] == avail[i-1]: continue
            back(path + [avail[i]], avail[:i] + avail[i+1:])
    back([], sorted(half))
    return res

function generatePalindromes(s) {
  const c = {};
  for (const ch of s) c[ch] = (c[ch] || 0) + 1;
  const oddKeys = Object.keys(c).filter(k => c[k] % 2);
  if (oddKeys.length > 1) return [];
  const mid = oddKeys[0] || "";
  const half = [];
  for (const k of Object.keys(c)) for (let i = 0; i < Math.floor(c[k] / 2); i++) half.push(k);
  half.sort();
  const res = [];
  function back(path, avail) {
    if (!avail.length) { const p = path.join(""); res.push(p + mid + p.split("").reverse().join("")); return; }
    for (let i = 0; i < avail.length; i++) {
      if (i && avail[i] === avail[i-1]) continue;
      back([...path, avail[i]], avail.slice(0, i).concat(avail.slice(i+1)));
    }
  }
  back([], half);
  return res;
}

class Solution {
    List res = new ArrayList<>();
    String mid = "";
    public List generatePalindromes(String s) {
        int[] c = new int[128];
        for (char ch : s.toCharArray()) c[ch]++;
        StringBuilder half = new StringBuilder();
        int odd = 0;
        for (int i = 0; i < 128; i++) {
            if (c[i] % 2 == 1) { odd++; mid = String.valueOf((char) i); }
            for (int j = 0; j < c[i] / 2; j++) half.append((char) i);
        }
        if (odd > 1) return res;
        char[] arr = half.toString().toCharArray();
        Arrays.sort(arr);
        back(arr, new StringBuilder(), new boolean[arr.length]);
        return res;
    }
    void back(char[] arr, StringBuilder cur, boolean[] used) {
        if (cur.length() == arr.length) {
            res.add(cur.toString() + mid + cur.reverse().toString());
            cur.reverse();
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (used[i]) continue;
            if (i > 0 && arr[i] == arr[i-1] && !used[i-1]) continue;
            used[i] = true; cur.append(arr[i]);
            back(arr, cur, used);
            used[i] = false; cur.deleteCharAt(cur.length() - 1);
        }
    }
}

class Solution {
    vector res;
    string mid;
    void back(string& arr, string& cur, vector& used) {
        if (cur.size() == arr.size()) {
            string rev(cur.rbegin(), cur.rend());
            res.push_back(cur + mid + rev);
            return;
        }
        for (int i = 0; i < (int)arr.size(); i++) {
            if (used[i]) continue;
            if (i && arr[i] == arr[i-1] && !used[i-1]) continue;
            used[i] = true; cur += arr[i];
            back(arr, cur, used);
            used[i] = false; cur.pop_back();
        }
    }
public:
    vector generatePalindromes(string s) {
        int c[128] = {0};
        for (char ch : s) c[ch]++;
        string half; int odd = 0;
        for (int i = 0; i < 128; i++) {
            if (c[i] % 2) { odd++; mid = string(1, (char) i); }
            half += string(c[i] / 2, (char) i);
        }
        if (odd > 1) return res;
        sort(half.begin(), half.end());
        string cur; vector used(half.size(), false);
        back(half, cur, used);
        return res;
    }
};

Explanation

A palindrome reads the same forwards and backwards, so the left half completely determines the right half. The big idea here is to only permute half the letters and then mirror them to build the full palindrome.

First we count each letter. A palindrome is possible only if at most one letter has an odd count; that odd letter (if any) becomes the single mid character. We then take half of every letter's count to form the half multiset.

Next we generate every distinct permutation of half with backtracking. To avoid repeats from equal letters, we sort half and skip a letter when it equals the previous one at the same level (if i and avail[i] == avail[i-1]). For each complete half p, the answer is p + mid + reverse(p).

Example: s = "aabb". Each letter appears twice (no odd one), so mid is empty and half = [a, b]. Permuting gives "ab" → abba and "ba" → baab.

Because we only permute half and mirror it, the work shrinks dramatically and every result is guaranteed to be a palindrome.

Time: O((n/2)!) Space: O((n/2)!)