267. Palindrome Permutation II

Problem Description

The problem asks for all unique permutations of a given string s that form a palindrome. A palindrome is a string that reads the same forwards and backwards. To solve this problem, you must generate all possible palindromic strings using the characters of s, ensuring that no duplicates are in the result. The order of the results is not important, so they can be returned in any sequence. If no palindromic permutations are possible from s, the result should be an empty list.

Intuition

To come up with a solution for palindromic permutations, consider the properties of a palindrome. In a palindrome, characters are mirrored around the center of the string. This means that the string must have an even count of each character, except possibly one character that can sit in the middle without a pair (for strings with an odd length). For instance, in the palindrome "abba", 'a' and 'b' both appear twice. In the palindrome "racecar", 'r', 'a', and 'c' appear twice, and 'e' appears once at the center.

With these observations, we can develop an algorithm in the following steps:

1. Count the occurrences of each character in the input string.
2. Check the counts of all characters.
   • If there is more than one character with an odd count, a palindromic permutation is not possible, and we return an empty list.
   • If there is one character with an odd count, it must be at the center of the permutation. If the string's length is even, there should not be any character with an odd count.
3. Using this count, we start constructing the palindromic strings. For a character that has an even count, we can place half of these characters on one side and the mirrored half on the other side with respect to the center of the string. For the character with an odd count, we place it in the middle.

In the implementation, a backtracking approach, which is a form of depth-first search (DFS), is utilized. Starting with an empty string or the middle character if the string length is odd, we add pairs of characters to the string until it is the same length as the input string. Every time we add a pair, we decrease the count of that character by two. We explore all possible character placements by trying out all characters with more than one remaining count. After exploring a character pairing, we backtrack and reset the count to ensure that we can explore a different pairing. The resulting strings are appended to a list, which contains our palindromic permutations.

The use of backtracking provides an efficient way to explore all valid combinations without generating duplicates. Since we add pairs of characters and check for an odd count of characters at the beginning, we guarantee the result will be palindromic and unique.

Learn more about Backtracking patterns.

Solution Approach

To implement the solution to the palindromic permutations problem, the code leverages the following concepts and structures:

1. Counter: To count the occurrences of each character in the string, Python's Counter from the collections module is utilized. The Counter creates a hash table where keys are characters from the string and values are counts of those characters.

2. Backtracking: The depth-first search (DFS) backtracking approach is used to explore the possibilities of building half of a palindromic string. Backtracking means that we build up partial solutions to the problem and abandon them ("backtrack") as soon as we can tell that they will not lead to a complete solution.

3. Recursive Function (dfs): The code defines a recursive helper function named dfs which builds a half-string t. This half-string represents half of a potential palindromic permutation.

4. Pruning: The search space is pruned early by checking if more than one character has an odd count. If this is the case, we return an empty list immediately since it's not possible to form a palindrome in such a scenario.

5. String Manipulation: For characters with a count greater than 1, the code appends the character to both the beginning and end of string t (c + t + c), effectively placing these characters in mirrored positions around the palindrome's center.

Here's a breakdown of the implementation steps:

1. Calculate the count of each character in s and store them in cnt.

2. Look for a middle character (only relevant for odd-length strings). If more than one character has an odd occurrence count, there cannot be any palindromic permutations, so return [].

3. Initialize an empty list ans to hold the final permutations.

4. Call the recursive function dfs starting with mid as the initial partial palindrome (empty string if even length, single character if odd length).

5. Within dfs, if the current string t reaches the length of s, it means a half palindrome is completed, and then it's appended to the list of results ans.

6. The inner logic of dfs iterates over the count dict items and tries to extend the string t by adding characters to both ends, decreasing the count by two since one character is placed on each side. This operation is done recursively until all characters have been used up.

7. For each recursive call, once returned, the character count is restored (incremented by two) to allow for the next permutation to be generated (backtracking part).

After exploring all possible permutations through backtracking, the function returns the list ans containing all unique palindromic permutations.

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the string "aabb".

1. Initialize Counter: First, we count occurrences of each character using Counter.

   Counter result: {'a': 2, 'b': 2}

   Since all character counts are even, palindromic permutations are possible.

2. Check for a Middle Character: The length of "aabb" is even, so we don't need a middle character. If there was an odd count of characters, the solution would directly return an empty list as that won't form a palindrome.

3. Backtracking Setup: We start with an empty list ans to store the unique permutations and an empty string mid.

4. Calling dfs: We call the recursive function dfs with arguments t = mid (initially an empty string) and our character count dictionary.

5. Building Half Palindromes: Inside dfs, we have these steps:

   • If the length of t is the same as half the length of s (len(s)/2), we have formed half of a palindrome. We mirror t around mid to form the full palindromic permutation and add it to ans.
   • Otherwise, we try to extend t:
     • For every character c with a count of 2 or more in our count dictionary, we append c to both the beginning and end of t to maintain the mirroring property of the palindrome (c + t + c). We recursively call dfs with this new string and updated counts (decremented by two).

6. Recursion and Backtracking: Every recursive call attempts to extend the palindrome by adding new pairs of characters. When it backtracks (returns to the previous call), it restores the count, allowing other pairs to be considered, exploring all possible palindromic permutations without repetition.

For "aabb", the function dfs will execute as follows:

• First call dfs(""):
  • Tries dfs("a" + "" + "a") leading to dfs("aa"), then since len(t) equals len(s)/2, adds "aabb" to ans.
  • Tries dfs("b" + "" + "b") leading to dfs("bb"), then since len(t) equals len(s)/2, adds "bbaa" to ans.

The final result ans will contain ["aabb", "bbaa"]. By mirroring t around mid if needed (not in this case as the length of s is even), we ensure the palindrome property is maintained. The backtracking algorithm ensures all unique combinations are explored without duplication.

Solution Implementation

Time and Space Complexity

The above Python code generates all possible palindromes from the given string by using a depth-first search approach. To analyze the time complexity and space complexity, we need to consider several factors:

• Let n be the length of the string s.
• The maximum number of half-palindromes we can generate is bound by n/2! since a palindrome can be constructed by placing the second half in reverse order of the first half, and the characters in the first half can be permuted.
• The dfs function is called recursively and generates palindromes by appending characters to both ends of a growing string t.
• The dfs function is only called if a character count v is greater than 1, and it reduces v by 2, enforcing the palindrome property.

Time Complexity

The time complexity is given by the product of the number of recursive calls dfs can make and the time taken per call.

• The unique characters in the string form the branching factor in our DFS call. Let's assume the number of unique characters is k.
• At each level of recursion, we loop over k characters but only recurse if their count is more than 1; otherwise, it leads to the base case.
• The dfs will execute at most n/2 levels deep as we are adding two characters per recursive call for palindrome construction.
• At each call new string t is constructed, which costs O(n) time.

Hence, the time complexity is approximately O((n/2)*k*(n/2)!), considering the permutations of a half-length palindrome and the time taken to construct each candidate.

Space Complexity

• The space complexity includes the space for the recursion call stack, which goes n/2 levels deep, and thus the space complexity here is O(n/2), which simplifies to O(n).
• We also use a dictionary cnt to store the character counts which, in the worst case, can contain unique counts for all n characters, also contributing O(n) space.
• The ans list could potentially have n/2! half-length palindromes.

Overall, the space complexity is O(n + n/2!), which simplifies to O(n/2!) considering that the factorial term will dominate for larger n.

Learn more about how to find time and space complexity quickly using problem constraints.