267. Palindrome Permutation II

MediumHash TableStringBacktracking
Leetcode Link

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1from collections import Counter
2from typing import List
3
4class Solution:
5    def generatePalindromes(self, s: str) -> List[str]:
6        # Helper function for depth-first search.
7        def dfs(palindrome_half):
8            # If the current string is of the same length as input string, it's a valid palindrome.
9            if len(palindrome_half) == len(s):
10                palindromes.append(palindrome_half)
11                return
12            # Attempt to add characters on both sides of the current palindrome half.
13            for char, count in char_count.items():
14                if count > 1:
15                    char_count[char] -= 2
16                    dfs(char + palindrome_half + char)
17                    char_count[char] += 2  # Backtrack.
18
19        char_count = Counter(s)
20        middle_char = ''  # Character to be put in the middle of the palindrome if any.
21        # Identify the middle character in the palindrome, if it exists.
22        for char, count in char_count.items():
23            if count % 2 != 0:
24                if middle_char:
25                    # More than one character with odd count means no palindrome possible.
26                    return []
27                middle_char = char
28                char_count[char] -= 1  # Update the count after placing it in the middle.
29
30        palindromes = []
31        dfs(middle_char)
32        return palindromes
33
34# Example usage:
35# solution = Solution()
36# palindromes = solution.generatePalindromes("aabb")
37# print(palindromes)  # Output will be all the palindrome combinations of the string "aabb"
38
1class Solution {
2    private List<String> palindromeList = new ArrayList<>(); // Store the generated palindromes
3    private int[] charCount = new int[26]; // Count of each character 'a' to 'z'
4    private int strLength; // Length of the input string
5
6    public List<String> generatePalindromes(String s) {
7        strLength = s.length(); // Initialize the length of the string
8      
9        // Populate the character count array with the frequency of each character in the string
10        for (char c : s.toCharArray()) {
11            charCount[c - 'a']++;
12        }
13      
14        String middle = ""; // To hold the middle character in case of an odd length palindrome
15      
16        // Check whether more than one character has an odd count, return empty list if true
17        for (int i = 0; i < 26; ++i) {
18            if (charCount[i] % 2 == 1) {
19                if (!middle.equals("")) {
20                    return palindromeList;
21                }
22                middle = String.valueOf((char) (i + 'a'));
23            }
24        }
25      
26        // Start the depth-first search with the middle character (empty if even length palindrome)
27        dfs(middle);
28        return palindromeList;
29    }
30
31    // Helper method to perform depth-first search to build palindromes
32    private void dfs(String current) {
33        // If the current string's length equals the original string length, it is a valid palindrome
34        if (current.length() == strLength) {
35            palindromeList.add(current);
36            return;
37        }
38      
39        for (int i = 0; i < 26; ++i) {
40            // If there are more than one of current character, add it to both ends of the string and continue the search
41            if (charCount[i] > 1) {
42                String character = String.valueOf((char) (i + 'a'));
43                charCount[i] -= 2; // Reduce count because we use two characters
44              
45                dfs(character + current + character); // Recursively call dfs with the updated string
46              
47                charCount[i] += 2; // Backtrack and restore the count for the next iteration
48            }
49        }
50    }
51}
52
1class Solution {
2public:
3    // The size of the input string.
4    int string_size;
5
6    // This vector will store our final palindrome permutations.
7    vector<string> possible_palindromes;
8
9    // A hash map to keep track of the character frequencies.
10    unordered_map<char, int> char_count;
11
12    // Entry function to generate possible palindromic permutations.
13    vector<string> generatePalindromes(string s) {
14        // Initialize the size of the string.
15        string_size = s.size();
16
17        // Counting the frequency of each character in the input string.
18        for (char c : s) ++char_count[c];
19
20        // 'middle_element' can only have one character in odd count for palindromes.
21        string middle_element = "";
22        for (auto& [character, frequency] : char_count) {
23            // If the frequency is odd and 'middle_element' is already set,
24            // it means we cannot form a palindrome.
25            if (frequency & 1) {
26                if (!middle_element.empty()) {
27                    return possible_palindromes; // Return as no palindromic permutations possible.
28                }
29                // Assign the middle element.
30                middle_element = character;
31            }
32        }
33
34        // Starting DFS with the potential middle element.
35        depthFirstSearch(middle_element);
36        return possible_palindromes;
37    }
38
39    // Helper function to perform depth-first search to generate palindromes.
40    void depthFirstSearch(string current_string) {
41        // If the current string's size matches the input size, we found a palindrome.
42        if (current_string.size() == string_size) {
43            possible_palindromes.push_back(current_string);
44            return;
45        }
46
47        // Construct new palindromes by adding characters around the 'current_string'.
48        for (auto& [character, frequency] : char_count) {
49            // We should have at least 2 characters to place around 'current_string'.
50            if (frequency > 1) {
51                frequency -= 2;
52                // Add the character on both sides of 'current_string' and recurse.
53                depthFirstSearch(character + current_string + character);
54                // Restore the count after the recursive call.
55                frequency += 2;
56            }
57        }
58    }
59};
60
1// The size of the input string.
2let stringSize: number;
3
4// This array will store our final palindrome permutations.
5let possiblePalindromes: string[] = [];
6
7// A map to keep track of the character frequencies.
8let charCount: Map<string, number> = new Map<string, number>();
9
10// Entry function to generate possible palindromic permutations.
11function generatePalindromes(s: string): string[] {
12    // Initialize the size of the string.
13    stringSize = s.length;
14    possiblePalindromes = [];
15    charCount.clear();
16
17    // Counting the frequency of each character in the input string.
18    for (let c of s) {
19        charCount.set(c, (charCount.get(c) || 0) + 1);
20    }
21
22    // 'middleElement' can only have one character in odd count for palindromes.
23    let middleElement = "";
24    for (let [character, frequency] of charCount) {
25        // If the frequency is odd and 'middleElement' is already set,
26        // it means we cannot form a palindrome.
27        if (frequency % 2 === 1) {
28            if (middleElement !== "") {
29                return possiblePalindromes; // Return as no palindromic permutations possible.
30            }
31            // Assign the middle element.
32            middleElement = character;
33        }
34    }
35
36    // Starting DFS with the potential middle element.
37    depthFirstSearch(middleElement);
38    return possiblePalindromes;
39}
40
41// Helper function to perform depth-first search to generate palindromes.
42function depthFirstSearch(currentString: string) {
43    // If the current string's size matches the input size, we found a palindrome.
44    if (currentString.length === stringSize) {
45        possiblePalindromes.push(currentString);
46        return;
47    }
48
49    // Construct new palindromes by adding characters around the 'currentString'.
50    for (let [character, frequency] of charCount) {
51        // We should have at least 2 characters to place around 'currentString'.
52        if (frequency > 1) {
53            charCount.set(character, frequency - 2);
54            // Add the character on both sides of 'currentString' and recurse.
55            depthFirstSearch(character + currentString + character);
56            // Restore the count after the recursive call.
57            charCount.set(character, frequency);
58        }
59    }
60}
61

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄