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:

  1. Count Characters: The solution starts by counting the occurrences of each character in the input string s using Counter from the collections module. This step is crucial to determine if a palindromic permutation is possible and to construct the permutations.

  2. 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.

  3. Depth-First Search (DFS): The dfs function is a recursive method that builds palindromic strings. It concatenates characters around a central mid string (which is empty or contains the single odd-count character). This function operates by:
    • Adding a character c to both ends of the current string t if c has more than one occurrence left (v > 1).
    • Reducing cnt[c] by 2 to account for using two instances of c.
    • Recursively calling dfs with the updated string.
    • Backtracking by restoring cnt[c] after the recursive call to explore other possibilities.

  4. Base Case and Collecting Results: When the length of the constructed string t matches the length of the input string s, a palindromic permutation has been completed, and it is added to the ans list.

  5. Initialization and First Call: Before calling dfs, the code handles the special case of the middle character for odd-length palindromes by decrementing its count and sets up the initial call to dfs with mid 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 if v 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 string t to ans without needing to copy it, as t 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
}

All Problems

All Solutions