Smallest Palindromic Rearrangement II solution and explanation
5 more videos on this problem
Smallest Palindromic Rearrangement II (Leetcode Weekly 445)Soumya Bhattacharjee · 13:33 · 802 views
3518. Smallest Palindromic Rearrangement II (Leetcode Hard)Programming Live with Larry · 48:56 · 403 views
Smallest Palindromic Rearrangement II | Leetcode Contest Solution | @Solution_spotSolution Spot · 0:37 · 350 views
Smallest Palindromic Rearrangement II | LeetCode 3518 | Weekly Contest 445 | Java | Developer CoderDeveloper Coder · 45:17 · 275 views
leetcode 3518 Smallest Palindromic Rearrangement II | BacktrackingCode-Yao · 25:00 · 181 views
Retry Leetcode 3518 Smallest Palindromic Rearrangement IILuc Taylor · 1:18:38 · 48 views
The problem
You are given a palindromic string s and an integer k.
Return the k-th lexicographically smallest palindromic permutation of s. If there are fewer than k distinct palindromic permutations, return an empty string.
Note: Different rearrangements that yield the same palindromic string are considered identical and are counted once.
Example 1:
Input: s = "abba", k = 2
Output: "baab"
Explanation:
- The two distinct palindromic rearrangements of
"abba"are"abba"and"baab". - Lexicographically,
"abba"comes before"baab". Sincek = 2, the output is"baab".
Example 2:
Input: s = "aa", k = 2
Output: ""
Explanation:
- There is only one palindromic rearrangement:
"aa". - The output is an empty string since
k = 2exceeds the number of possible rearrangements.
Example 3:
Input: s = "bacab", k = 1
Output: "abcba"
Explanation:
- The two distinct palindromic rearrangements of
"bacab"are"abcba"and"bacab". - Lexicographically,
"abcba"comes before"bacab". Sincek = 1, the output is"abcba".
Constraints:
1 <= s.length <= 104sconsists of lowercase English letters.sis guaranteed to be palindromic.1 <= k <= 106
Approach overview
Problem Overview: You are given a string and must rearrange its characters to form palindromes. Among all valid palindromic rearrangements, return the k-th lexicographically smallest one. If fewer than k palindromes exist, return an empty string. The challenge is efficiently counting how many palindromes can be formed from the remaining characters while constructing the answer.
Approach 1: Generate All Palindromic Permutations (Brute Force) (Time: O(n! * n), Space: O(n!))
Start by counting character frequencies using a hash table. If more than one character has an odd frequency, forming a palindrome is impossible. Otherwise, build the half-string containing freq[c] / 2 copies of each character. Generate all permutations of this half-string, mirror them around the center character (if one exists), and store the resulting palindromes. After sorting lexicographically, return the k-th palindrome. This approach demonstrates the palindrome construction logic but quickly becomes infeasible because permutations grow factorially.
Approach 2: Lexicographic Construction with Combinatorics (Optimal) (Time: O(26 * n), Space: O(26))
Instead of generating every permutation, compute how many palindromes can be formed from the remaining characters. Count character frequencies with a hash table and build the half-frequency array. The palindrome is determined entirely by the order of this half. Iterate characters from 'a' to 'z' and tentatively place one character in the current position of the half-string. Use combinatorics to calculate how many permutations remain with the updated counts using factorial division: (remaining)! / (freq1! * freq2! ...). If this count is smaller than k, skip those permutations and subtract from k. Otherwise, fix that character and continue building the half. After the half-string is finalized, mirror it and insert the optional middle character to produce the full palindrome. This avoids generating permutations and relies on counting instead.
The core idea is treating palindrome construction as a permutation problem on half the characters. Efficient counting lets you skip entire blocks of permutations and directly construct the desired result.
Recommended for interviews: The combinatorics-based lexicographic construction is the expected approach. Brute force shows you understand how palindromes form, but interviewers typically look for the counting insight that avoids enumerating permutations. Combining string manipulation with combinatorial counting demonstrates strong algorithmic reasoning.
Solution
impl Solution {
pub fn smallest_palindrome(s: String, k: i32) -> String {
let bytes = s.as_bytes();
let rank = k.max(1) as usize;
const COUNT_LIMIT: usize = 1_000_001;
let mut frequencies = [0usize; 26];
for &byte in bytes {
frequencies[(byte - b'a') as usize] += 1;
}
let mut odd_count = 0usize;
let mut middle_char_index = 26u8;
for char_index in 0..26 {
if frequencies[char_index] & 1 == 1 {
odd_count += 1;
middle_char_index = char_index as u8;
}
}
if odd_count > 1 {
return String::new();
}
let mut half_frequencies = [0usize; 26];
let mut half_length = 0usize;
for char_index in 0..26 {
half_frequencies[char_index] = frequencies[char_index] / 2;
half_length += half_frequencies[char_index];
}
let count_permutations = |counts: &[usize; 26]| -> usize {
let mut remaining: usize = counts.iter().sum();
let mut permutations = 1usize;
for &count in counts {
if count == 0 {
continue;
}
let selected = count.min(remaining - count);
let mut combinations = 1usize;
for step in 1..=selected {
combinations = combinations * (remaining - step + 1) / step;
if combinations >= COUNT_LIMIT {
combinations = COUNT_LIMIT;
break;
}
}
permutations *= combinations;
if permutations >= COUNT_LIMIT {
return COUNT_LIMIT;
}
remaining -= count;
}
permutations
};
if rank > count_permutations(&half_frequencies) {
return String::new();
}
let length = bytes.len();
let mut palindrome = vec![0u8; length];
let mut remaining_rank = rank;
let mut position = 0usize;
for _ in 0..half_length {
for char_index in 0..26 {
if half_frequencies[char_index] == 0 {
continue;
}
half_frequencies[char_index] -= 1;
let suffix_count = count_permutations(&half_frequencies);
if suffix_count >= remaining_rank {
palindrome[position] = char_index as u8 + b'a';
position += 1;
break;
}
remaining_rank -= suffix_count;
half_frequencies[char_index] += 1;
}
}
if middle_char_index < 26 {
palindrome[half_length] = middle_char_index + b'a';
}
for index in 0..half_length {
palindrome[length - 1 - index] = palindrome[index];
}
String::from_utf8(palindrome).unwrap()
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Palindromic Permutations | O(n! * n) | O(n!) | Educational approach for understanding palindrome construction; impractical for large inputs |
| Lexicographic Construction with Combinatorics | O(26 * n) | O(26) | Best approach for large strings; counts permutations and skips blocks efficiently |
Frequently asked questions
Is Smallest Palindromic Rearrangement II easy or hard?
Smallest Palindromic Rearrangement II is classified as Hard because it combines multiple concepts: palindrome feasibility checks, lexicographic ordering, and combinatorial permutation counting. Implementing the counting logic correctly while maintaining efficiency is the main challenge.
Smallest Palindromic Rearrangement II Python/Java solution
Implementations in Python, Java, C++, and Go follow the same pattern: compute character frequencies, build the half-string counts, and iteratively select characters while updating permutation counts. The key part of the code calculates factorial-based combinations to determine how many palindromes remain for each candidate choice.
How to solve Smallest Palindromic Rearrangement II in O(n)?
First count character frequencies and verify that at most one character has an odd count. Build the half-frequency array and construct the half-string one character at a time. At each step, use combinatorial counting to determine how many palindromes are possible if a character is chosen. Skip groups of permutations until the k-th position is reached, then mirror the half to form the final palindrome.
What is the best approach for Smallest Palindromic Rearrangement II?
The best approach uses combinatorics with frequency counting. Count character frequencies, construct the half of the palindrome, and iteratively choose characters in lexicographic order. For each candidate character, compute how many palindromic permutations remain using factorial-based counting. This allows skipping entire groups of permutations and directly building the k-th palindrome.
Is Smallest Palindromic Rearrangement II asked at Google/Amazon/Meta?
Problems combining permutation counting, palindrome construction, and lexicographic ordering appear in interviews at companies like Google, Amazon, and Meta. Variants involving k-th permutation or combinatorial counting are common because they test both mathematical reasoning and efficient string manipulation.
What data structure is used in Smallest Palindromic Rearrangement II?
A hash table or fixed-size frequency array is used to store character counts. The algorithm also relies on factorial values for combinatorial counting. Together these structures allow efficient tracking of remaining characters and calculation of permutation counts.
What is the time complexity of Smallest Palindromic Rearrangement II?
The optimal combinatorics approach runs in O(26 * n) time because each position in the half-string checks at most 26 characters and performs constant-time counting operations. Space complexity is O(26) for storing character frequencies. Brute force permutation generation takes O(n! * n) time and is not practical.