Welcome to Subscribe On Youtube
267. Palindrome Permutation II
Description
Given a string s, return all the palindromic permutations (without duplicates) of it.
You may return the answer in any order. If s
has no palindromic permutation, return an empty list.
Example 1:
Input: s = "aabb" Output: ["abba","baab"]
Example 2:
Input: s = "abc" Output: []
Constraints:
1 <= s.length <= 16
s
consists of only lowercase English letters.
Solutions
Key Concepts and Steps:

Count Characters: The solution starts by counting the occurrences of each character in the input string
s
usingCounter
from thecollections
module. This step is crucial to determine if a palindromic permutation is possible and to construct the permutations. 
Check for Palindrome Possibility: A string can be permuted into a palindrome if at most one character has an odd count. The loop through
cnt.items()
checks for this condition. If more than one character has an odd count, it returns an empty list, as no palindromic permutation is possible. If exactly one character has an odd count, it is designated as the middle character (mid
) of the palindrome.  DepthFirst Search (DFS): The
dfs
function is a recursive method that builds palindromic strings. It concatenates characters around a centralmid
string (which is empty or contains the single oddcount character). This function operates by: Adding a character
c
to both ends of the current stringt
ifc
has more than one occurrence left (v > 1
).  Reducing
cnt[c]
by 2 to account for using two instances ofc
.  Recursively calling
dfs
with the updated string.  Backtracking by restoring
cnt[c]
after the recursive call to explore other possibilities.
 Adding a character

Base Case and Collecting Results: When the length of the constructed string
t
matches the length of the input strings
, a palindromic permutation has been completed, and it is added to theans
list.  Initialization and First Call: Before calling
dfs
, the code handles the special case of the middle character for oddlength palindromes by decrementing its count and sets up the initial call todfs
withmid
as the starting string.
Important Observations:
 The solution efficiently constructs palindromic permutations by ensuring symmetry around the middle character.
 It leverages backtracking to explore all valid permutations without repeating characters more times than they occur in the input string.
 The check for
if v & 1
uses bitwise AND to determine ifv
is odd, contributing to the determination of the middle character of the palindrome.  The decrement
cnt[c] = 1
after finding the middle character ensures that when the DFS starts, the counts accurately reflect the characters available for constructing the two halves of the palindrome. ans.append(t)
directly appends the constructed stringt
toans
without needing to copy it, ast
is newly created in each recursive call.
Complexity:
 The time complexity is difficult to determine precisely due to the recursive generation of permutations but is heavily influenced by the number of unique characters and their counts.
 The space complexity is primarily affected by the storage of the palindromic permutations in
ans
, which can grow exponentially with the size of the input string for certain distributions of characters.

class Solution { private List<String> ans = new ArrayList<>(); private int[] cnt = new int[26]; private int n; public List<String> generatePalindromes(String s) { n = s.length(); for (char c : s.toCharArray()) { ++cnt[c  'a']; } String mid = ""; for (int i = 0; i < 26; ++i) { if (cnt[i] % 2 == 1) { if (!"".equals(mid)) { return ans; } mid = String.valueOf((char) (i + 'a')); } } dfs(mid); return ans; } private void dfs(String t) { if (t.length() == n) { ans.add(t); return; } for (int i = 0; i < 26; ++i) { if (cnt[i] > 1) { String c = String.valueOf((char) (i + 'a')); cnt[i] = 2; dfs(c + t + c); cnt[i] += 2; } } } }

class Solution { public: int n; vector<string> ans; unordered_map<char, int> cnt; vector<string> generatePalindromes(string s) { n = s.size(); for (char c : s) ++cnt[c]; string mid = ""; for (auto& [k, v] : cnt) { if (v & 1) { if (mid != "") { return ans; } mid += k; } } dfs(mid); return ans; } void dfs(string t) { if (t.size() == n) { ans.push_back(t); return; } for (auto& [k, v] : cnt) { if (v > 1) { v = 2; dfs(k + t + k); v += 2; } } } };

''' >>> "sss".copy() Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'str' object has no attribute 'copy' ''' class Solution: def generatePalindromes(self, s: str) > List[str]: def dfs(t): if len(t) == len(s): ans.append(t) # not using t.copy() 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 # don't forget this # actually, above is cheking 'if v > 1:', so good without this line ans = [] dfs(mid) return ans

func generatePalindromes(s string) []string { cnt := map[byte]int{} for i := range s { cnt[s[i]]++ } mid := "" ans := []string{} for k, v := range cnt { if v%2 == 1 { if mid != "" { return ans } mid = string(k) } } var dfs func(t string) dfs = func(t string) { if len(t) == len(s) { ans = append(ans, t) return } for k, v := range cnt { if v > 1 { cnt[k] = 2 c := string(k) dfs(c + t + c) cnt[k] += 2 } } } dfs(mid) return ans }