Smallest Palindromic Rearrangement II — 🟡 Intermediate (2/3) — LeetCode Daily Python Solution (stop building the whole string)

Introduction

Some problems test whether you know a data structure. This one tests something rarer: whether you notice when you're about to do ten times more work than you need to.

Smallest Palindromic Rearrangement II looks intimidating on the surface — you're asked to find the k-th smallest palindrome you can build from a string's letters, out of potentially millions of arrangements. The naive instinct is to generate them all, sort them, and index in. That instinct is exactly what interviewers are probing for, because it works on paper and collapses the moment the input gets realistic.

The real skill being tested here is combinatorial thinking: can you count arrangements without listing them? Can you exploit structure (a palindrome mirrors itself) to cut your problem in half before you've written a single line of generation code? This pattern — rank the k-th item in a huge combinatorial space using factorials instead of enumeration — shows up constantly in interviews, from permutation-rank problems to scheduling problems to cryptographic key-space reasoning. Learning it once here pays off well beyond this specific LeetCode problem.

Problem Overview

You're given a string s that is already a palindrome, and an integer k. Your job is to consider every distinct way you can rearrange the letters of s such that the result is also a palindrome, sort all of those distinct palindromic rearrangements alphabetically, and return the one at position k (1-indexed).

If there aren't k distinct palindromic rearrangements available, you return an empty string.

Two details matter a lot here:

• "Distinct" — if letters repeat, some rearrangements will look identical to each other. You're ranking unique strings, not raw permutations.
• s is guaranteed to already be a palindrome — which tells you something important for free: at most one letter has an odd count. That's a structural guarantee, not something you need to check for or handle as an edge case.

Example

Take s = "abba", k = 2.

The letter counts are a: 2, b: 2 — both even, so there's no letter that needs to sit alone in the middle. Every palindromic rearrangement of these letters:

• abba
• baab

Sorted alphabetically, that's ["abba", "baab"]. k = 2 means the second one: baab.

Now a trickier one: s = "cbabc", k = 2.

Letter counts: a: 1, b: 2, c: 2. The a is the odd one out — it has to sit in the exact middle. The b and c each split evenly, one copy into the left half, one mirrored into the right half.

That means the left half only ever contains one b and one c. The possible left halves, sorted alphabetically, are bc and cb. k = 2 picks cb. Mirror it around the middle a: cb + a + reverse(cb) = cb + a + bc = cbabc.

Notice what just happened: we never touched the full 5-character string's permutation space. We ranked a 2-character half.

Intuition

Here's the click moment an experienced engineer has almost immediately: a palindrome is entirely determined by its first half. The second half isn't independent information — it's a forced mirror of the first. So if you're going to rank palindromic rearrangements, you don't need to rank 5-character strings, you need to rank 2-character strings (roughly half the length), and the rest writes itself.

This reframes the whole problem. Instead of "list every palindrome and sort," it becomes "rank the left half like you'd rank the k-th permutation of a multiset." That's a well-known sub-problem: given a bag of letters, what's the k-th smallest arrangement, without generating all arrangements?

The tool for that is the classic "counting in a mixed-radix system" trick. When you rank permutations of distinct items, you use factorials: fix the first character, and there are (n-1)! ways to arrange the rest. When items repeat, you divide by the factorial of each letter's count — the standard multiset permutation formula:

distinct arrangements = n! / (count(a)! * count(b)! * ... )

That formula is the whole engine. It lets you ask, "if I place letter X in this position, how many valid completions exist?" — as a single calculation, not a loop that builds and counts every completion.

The odd-count letter (if it exists) is simply set aside first: it never enters the ranking at all, it just gets slotted into the exact middle once the left half is decided.

Brute Force Solution

Idea: Generate every permutation of s, filter for the ones that are palindromes, deduplicate, sort, and index.

Algorithm:

1. Use itertools.permutations(s) to generate all orderings.
2. Filter to keep only strings equal to their own reverse.
3. Put them in a set to remove duplicates.
4. Sort the set alphabetically.
5. Return the k-th element, or "" if there aren't enough.

Advantages:

• Trivial to write and reason about.
• Easy to verify correctness on small, hand-checked inputs.

Disadvantages:

• itertools.permutations on a string of length n produces n! results — for just 10 characters that's over 3.6 million permutations, most of which get thrown away immediately because they aren't palindromes.
• Deduplicating with a set means holding potentially huge numbers of strings in memory simultaneously.
• Completely infeasible once n grows past roughly a dozen characters.

Time complexity: O(n! · n) — generating all permutations, each of length n, plus the palindrome check and dedup overhead. Space complexity: O(n! · n) in the worst case, to store the deduplicated set.

Optimal Solution

The optimal approach builds only the left half, using factorial-based ranking, then mirrors it. Here's the step-by-step shape:

Step 1 — Count letters. Build a frequency map of every character in s.

Step 2 — Isolate the odd-count letter. Since s is guaranteed to be a palindrome, at most one letter has an odd count. Pull it out — it will be the middle character (or there is none, if n is even). Every other letter's count gets halved: half goes into a "half multiset" that we'll rank and place, the other half is implied by mirroring.

Step 3 — Check feasibility. Using the multiset permutation formula, compute the total number of distinct arrangements of the half-multiset. If k is larger than this total, return "" immediately — no work needs to be done.

Step 4 — Greedily build the left half, one position at a time. For each position, try each available letter (in alphabetical order). For a candidate letter, compute how many distinct completions are possible if that letter goes here (again, using the multiset formula on the remaining letters). If k fits within that count, commit to the letter, move to the next position. If not, subtract that block of arrangements from k and try the next letter.

This is precisely the mixed-radix counting logic from the intuition section, expressed as a table for cbabc, k=2, half-multiset {b:1, c:1}:

Position	Candidate	Completions if chosen	k before	Decision
0	b	1 (bc is the only completion)	2	2 > 1, skip; k -= 1 → k=1
0	c	1 (cb)	1	1 ≤ 1, commit c
1	b	1	1	1 ≤ 1, commit b

Result: left half = "cb".

Step 5 — Mirror. Final answer = left half + (middle character, if any) + reverse(left half).

Python Code

from collections import Counter
from math import factorial


def kth_palindrome(s: str, k: int) -> str:
    counts = Counter(s)

    # Pull out the single odd-count letter (if any) for the middle.
    middle = ""
    for ch, cnt in counts.items():
        if cnt % 2 == 1:
            middle = ch
            counts[ch] -= 1
            break

    # Halve every remaining count to get the "half multiset".
    half_counts = {ch: cnt // 2 for ch, cnt in counts.items() if cnt > 0}
    half_len = sum(half_counts.values())

    def count_arrangements(letter_counts: dict, length: int) -> int:
        total = factorial(length)
        for cnt in letter_counts.values():
            total //= factorial(cnt)
        return total

    total_arrangements = count_arrangements(half_counts, half_len)
    if k > total_arrangements:
        return ""

    # Greedily build the left half, letter by letter, position by position.
    remaining = dict(half_counts)
    left_half = []
    for _ in range(half_len):
        for letter in sorted(remaining):
            if remaining[letter] == 0:
                continue
            remaining[letter] -= 1
            arrangements = count_arrangements(remaining, half_len - len(left_half) - 1)
            if k <= arrangements:
                left_half.append(letter)
                break
            k -= arrangements
            remaining[letter] += 1  # undo, try the next letter

    left = "".join(left_half)
    return left + middle + left[::-1]

Code Walkthrough

• Counter(s) builds the frequency map in one pass — O(n).
• The loop that finds the odd-count letter relies on the palindrome guarantee: there's never more than one, so we break the moment we find it and immediately decrement its count by one (removing the "middle" copy from further consideration).
• half_counts divides every remaining count by two with integer division — since we already removed the one odd count, every remaining count is guaranteed even.
• count_arrangements is the multiset permutation formula: n! divided by the factorial of each letter's count. This single function replaces any need to generate strings to count them.
• total_arrangements gives us the feasibility check up front — if k exceeds it, we bail before doing any placement work.
• The main loop walks each position of the left half. For each candidate letter (tried in sorted order, which is what guarantees alphabetical output), we tentatively use one copy, compute how many valid completions remain, and compare against k.
• If k fits, we keep the letter and move to the next position. If not, we "give back" the letter (remaining[letter] += 1) and subtract the block size from k, since we've now skipped past every arrangement that would have started with that letter here.
• The final line assembles the palindrome: left half, then the middle character (empty string if there wasn't one), then the left half reversed.

Dry Run

Using s = "cbabc", k = 2:

1. counts = {c:2, b:2, a:1}. a has odd count → middle = "a", counts["a"] -= 1 → counts["a"] = 0.
2. half_counts = {c:1, b:1} (halving 2→1 for both), half_len = 2.
3. total_arrangements = count_arrangements({c:1,b:1}, 2) = 2! / (1! * 1!) = 2. k=2 ≤ 2, so we proceed.
4. Position 0: try b first (alphabetical). Tentatively remaining = {c:1, b:0}. Completions with 1 slot left = 1!/1! = 1. k=2 > 1, so skip: k -= 1 → k=1, restore remaining["b"] = 1. Try c next. Tentatively remaining = {c:0, b:1}. Completions = 1!/1! = 1. k=1 ≤ 1, commit c. left_half = ["c"].
5. Position 1: only b remains. Commit it. left_half = ["c", "b"].
6. left = "cb". Result = "cb" + "a" + "bc" = "cbabc".

Matches our hand-traced example exactly.

Complexity Analysis

Time: O(half_len² · alphabet_size), roughly O(n²) in the worst case for a string of length n, since for each of the n/2 positions we may try up to 26 letters, and each trial computes a factorial-based formula over the remaining counts (bounded by alphabet size, not n). This is correct because we've replaced "generate and filter" with "compute a closed-form count" at every decision point — no enumeration ever happens.

Space: O(n) — for the counters and the accumulated left-half list. We never store more than one candidate string in memory.

Compare this to brute force's O(n!) — for a string of length 20, the difference is the gap between "instant" and "the sun burns out first."

Alternative Solutions

A middle-ground approach: generate palindromic rearrangements lazily using a min-heap or recursive backtracking with pruning, stopping once you've produced the k-th one. This avoids building the entire set upfront, so it's better than raw brute force, but it still does O(k) work in the worst case — if k is large (which it's allowed to be, given the constraints), this degrades toward the same blowup as full generation. The factorial-ranking approach is strictly better because its cost depends on string length, not on k itself.

Edge Cases

• Empty string: s = "" — no letters, one trivial "arrangement" (the empty string itself). k must be exactly 1.
• All identical characters: s = "aaaa" — only one distinct arrangement exists. Any k other than 1 returns "".
• Odd-length string, single unique letter with odd count elsewhere: verify the middle character is excluded from the half-multiset ranking entirely — a common bug is accidentally including it in half_counts.
• k exactly equal to the total arrangement count: should return the largest (last alphabetically) valid palindrome, not fail off-by-one.
• k larger than total arrangements: must return "", not throw an index error or return a partially built string.

Common Mistakes

1. Forgetting to exclude the middle letter from the half-multiset, which throws off every count computation downstream.
2. Off-by-one errors in the greedy loop — comparing k <= arrangements versus k < arrangements will silently shift every answer by one position.
3. Not restoring remaining[letter] after a failed trial, corrupting the counts used for later positions.
4. Iterating letters in insertion order instead of sorted order — since Python dicts preserve insertion order, forgetting sorted() breaks the alphabetical guarantee.
5. Recomputing factorials from scratch inside a tight loop without caching, which is fine at this problem's scale but becomes a real bottleneck if reused elsewhere on very long strings — worth knowing math.factorial is already implemented in optimized C, so caching only matters if you're calling it an extreme number of times.
6. Assuming brute force is "fine for now" and not revisiting it once the input size in the actual constraints is checked — the crossover point arrives much sooner than people expect.

Interview Questions

• How would you modify this to return the k-th smallest rearrangement that is not necessarily a palindrome?
• What changes if the alphabet isn't just lowercase English letters — say, arbitrary Unicode?
• Can you compute the rank of a given palindrome (the inverse operation) using the same technique?
• How would you handle extremely large k values that exceed standard integer ranges in other languages?
• What's the largest n for which brute force would still complete in under a second, roughly?

Similar Problems

• Permutation Sequence (LeetCode) — the direct ancestor of this technique: ranking the k-th permutation of a set of distinct digits using factorial counting.
• Next Permutation (LeetCode) — builds the same intuition about ordering permutations without generating all of them.
• Palindrome Permutation (LeetCode) — the prerequisite check for whether any palindromic rearrangement exists at all.
• Smallest Palindromic Rearrangement I (if it precedes this one in a series) — establishes the mirror-half concept in a simpler, non-ranking context.

Key Takeaways

A palindrome is fully described by half its characters — exploit that before you touch generation logic. Ranking without generating is a factorial-counting problem, not a searching problem: ask "how many completions does this choice allow?" instead of "let me build them and see." And always sanity-check brute force against realistic input sizes before trusting that it'll hold up in production or on a whiteboard.

Watch the Video

For the full walkthrough with visual diagrams of the greedy placement and the factorial counting in action, watch the video here: {LINK}

About the Series

This is part of Fun with Learning Technology, a daily series breaking down LeetCode problems with a focus on the why behind each solution — not just the code, but the thinking that gets you there. New problems drop daily, always with the same goal: build real algorithmic intuition, not memorized templates.

Call To Action

If this breakdown saved you from writing a brute-force solution that would've timed out, hit like on the video and subscribe on YouTube for tomorrow's daily drop. Subscribe to the Substack for the full written breakdowns delivered straight to your inbox. Drop a comment with how you'd extend this to non-palindromic k-th rearrangements — and share this with anyone prepping for interviews who still reaches for itertools.permutations first.

---

result = []
remaining = n
for _ in range(n):
    for c in sorted(half):
        if half[c] == 0:
            continue
        half[c] -= 1
        cnt = arrangements(half, remaining - 1)
        if k <= cnt:
            result.append(c)
            remaining -= 1
            break
        k -= cnt
        half[c] += 1