Question

Formatted question description: https://leetcode.ca/all/267.html

 267	Palindrome Permutation II

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

 For example:

 Given s = "aabb", return ["abba", "baab"].

 Given s = "abc", return [].

 Hint:

 If a palindromic permutation exists, we just need to generate the first half of the string.
 To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

Algorithm

One thing to note is that if you use an array to save the result directly, and if there are repeated characters in t, there may be duplicates, such as t = “baa”, then the final result will have duplicates

When start=0 and i=1, aba is obtained after the exchange,
Later when start=1 and i=2, aab can be obtained after the exchange.
But after returning to the first layer after baa, when start=0, i=2, aab is obtained after the exchange, and repetition occurs.

In fact, the easiest way to de-duplicate is to define the result res as a HashSet, and use its de-duplication feature to ensure that there is no duplicate.

Code

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Palindrome_Permutation_II {
    public static void main(String[] args) {
        Palindrome_Permutation_II out = new Palindrome_Permutation_II();
        Solution s = out.new Solution();

        System.out.println(s.generatePalindromes("aabb"));
        System.out.println(s.generatePalindromes("aaaa"));
        System.out.println(s.generatePalindromes("aaaaa"));
    }

    public class Solution_lesscode {
        public List<String> generatePalindromes(String s) {
            int[] cha = new int [256];
            for (int i = 0; i < s.length(); i ++) {
                cha[s.charAt(i)] += 1;
            }
            List<String> result = new LinkedList<String>();
            boolean odd = false;
            int oddIndex = 0;
            for (int i = 0; i < 256; i ++) {
                if (cha[i] % 2 == 1) {
                    if (odd == true) {
                        return result;
                    }
                    oddIndex = i;
                    odd = true;
                }
            }

            String base = "";
            if (odd == true) {
                base = (char)oddIndex + "";
                cha[oddIndex] -= 1;
            }
            process(base, cha, s.length(), result);
            return result;
        }
        private void process(String base, int[] cha, int n, List<String> result) {
            if (base.length() == n) {
                result.add(base);
                return;
            }
            for (int i = 0; i < cha.length; i ++) {
                if (cha[i] > 0) {
                    cha[i] -= 2;
                    process((char)i + base + (char)i, cha, n, result);
                    cha[i] += 2;
                }
            }
        }
    }

    class Solution {
        public List<String> generatePalindromes(String s) {

            List<String> result = new ArrayList<>();

            int odd = 0;

            // char => its count
            Map<Character, Integer> map = new HashMap<>();

            // step 1. build character count map and count odds
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                map.put(c, 1 + map.getOrDefault(c, 0));
                odd += map.get(c) % 2 != 0 ? 1 : -1;
            }

            // cannot form any palindromic string
            if (odd > 1) {
                return result;
            }

            // step 2. add half count of each character to list
            String mid = "";
            List<Character> charList = new ArrayList<>();
            for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                char key = entry.getKey();
                int val = entry.getValue();

                if (val % 2 != 0) { // odd count char
                    mid += key;
                }

                for (int i = 0; i < val / 2; i++) {
                    charList.add(key);
                }
            }

            // step 3. generate all the permutations
            getPerm(charList, mid, new boolean[charList.size()], new StringBuilder(), result);

            return result;
        }

        // generate all unique permutation from list, sb: cur_res
        void getPerm(List<Character> list, String midChar, boolean[] used, StringBuilder sb, List<String> result) {
            if (sb.length() == list.size()) {
                // form the palindromic string
                result.add(sb.toString() + midChar + sb.reverse().toString());
                sb.reverse(); // restore
                return;
            }

            for (int i = 0; i < list.size(); i++) {
                // avoid duplication
                if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) { // i-1 must already checked, so skip used[i - 1]==false
                    continue;
                }

                if (!used[i]) {
                    used[i] = true;
                    sb.append(list.get(i));
                    // recursion
                    getPerm(list, midChar, used, sb, result);
                    // backtracking
                    used[i] = false;
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
    }
}

```
Todo
```

class Solution:
    def generatePalindromes(self, s: str) -> List[str]:
        def dfs(t):
            if len(t) == len(s):
                ans.append(t)
                return
            for c, v in cnt.items():
                if v > 1:
                    cnt[c] -= 2
                    dfs(c + t + c)
                    cnt[c] += 2

        cnt = Counter(s)
        mid = ''
        for c, v in cnt.items():
            if v & 1:
                if mid:
                    return []
                mid = c
                cnt[c] -= 1
        ans = []
        dfs(mid)
        return ans

############

import collections


class Solution(object):
  def generatePalindromes(self, s):
    """
    :type s: str
    :rtype: List[str]
    """

    def helper(s, path, ans, visited):
      if len(path) == len(s):
        ans.append("".join(path))
        return

      for i in range(len(s)):
        if i > 0 and s[i] == s[i - 1] and i - 1 not in visited or i in visited:
          continue
        visited |= {i}
        path.append(s[i])
        helper(s, path, ans, visited)
        path.pop()
        visited -= {i}

    ans = []
    res = []
    ss = ""
    mid = ""
    counter = collections.Counter(s)
    oddChars = filter(lambda x: counter[x] % 2 == 1, counter)
    if len(s) % 2 == 1:
      if len(oddChars) == 1:
        mid = oddChars[0]
        counter[mid] -= 1
      else:
        return []
    elif len(oddChars) > 0:
      return []

    for key in counter:
      ss += key * (counter[key] / 2)

    helper(sorted(ss), [], res, set())
    for hword in res:
      ans.append(hword + mid + hword[::-1])
    return ans

267 - Palindrome Permutation II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions