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.
Flowchart Walkthrough
Let's analyze LeetCode 267. Palindrome Permutation II using the Flowchart. Here's a step-by-step walkthrough:
-
Is it a graph?
- No: The problem does not involve graphs; it focuses on generating permutations of strings.
-
Need to solve for kth smallest/largest?
- No: The problem is not about finding the kth smallest or largest element.
-
Involves Linked Lists?
- No: It does not involve operations related to Linked Lists.
-
Does the problem have small constraints?
- Yes: The problem likely involves small constraints because it deals with generating all permutations of a string, which is feasible only with small-sized strings due to factorial growth in possibilities.
-
Brute force / Backtracking?
- Yes: Since we're looking at generating permutations that can form a palindrome (a specific order rearrangement), brute force or backtracking is required to explore all valid permutations.
Conclusion: The flowchart suggests using a backtracking approach to generate all palindrome permutations of the string, ensuring each character's placements adhere to palindrome properties. This aligns well with the needs of the problem.
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:
- Count the occurrences of each character in the input string.
- 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.
- 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:
-
Counter: To count the occurrences of each character in the string, Python's
Counter
from thecollections
module is utilized. TheCounter
creates a hash table where keys are characters from the string and values are counts of those characters. -
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.
-
Recursive Function (
dfs
): The code defines a recursive helper function nameddfs
which builds a half-stringt
. This half-string represents half of a potential palindromic permutation. -
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.
-
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:
-
Calculate the count of each character in
s
and store them incnt
. -
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
[]
. -
Initialize an empty list
ans
to hold the final permutations. -
Call the recursive function
dfs
starting withmid
as the initial partial palindrome (empty string if even length, single character if odd length). -
Within
dfs
, if the current stringt
reaches the length ofs
, it means a half palindrome is completed, and then it's appended to the list of resultsans
. -
The inner logic of
dfs
iterates over the count dict items and tries to extend the stringt
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. -
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 EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach using the string "aabb"
.
-
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.
-
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. -
Backtracking Setup: We start with an empty list
ans
to store the unique permutations and an empty stringmid
. -
Calling
dfs
: We call the recursive function dfs with argumentst = mid
(initially an empty string) and our character count dictionary. -
Building Half Palindromes: Inside
dfs
, we have these steps:- If the length of
t
is the same as half the length ofs
(len(s)/2
), we have formed half of a palindrome. We mirrort
aroundmid
to form the full palindromic permutation and add it toans
. - Otherwise, we try to extend
t
:- For every character
c
with a count of 2 or more in our count dictionary, we appendc
to both the beginning and end oft
to maintain the mirroring property of the palindrome (c + t + c
). We recursively calldfs
with this new string and updated counts (decremented by two).
- For every character
- If the length of
-
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 todfs("aa")
, then sincelen(t)
equalslen(s)/2
, adds "aabb" toans
. - Tries
dfs("b" + "" + "b")
leading todfs("bb")
, then sincelen(t)
equalslen(s)/2
, adds "bbaa" toans
.
- Tries
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 strings
. - 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 stringt
. - The
dfs
function is only called if a character countv
is greater than 1, and it reducesv
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 mostn/2
levels deep as we are adding two characters per recursive call for palindrome construction. - At each call new string
t
is constructed, which costsO(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 isO(n/2)
, which simplifies toO(n)
. - We also use a dictionary
cnt
to store the character counts which, in the worst case, can contain unique counts for alln
characters, also contributingO(n)
space. - The
ans
list could potentially haven/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.
Which of the following is a good use case for backtracking?
Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.