Smallest Palindromic Rearrangement I — 🔴 Advanced (3/3) — LeetCode Daily Python Solution (why not just try every order?)

Introduction

Palindrome problems show up constantly in coding interviews because they test something more specific than "can you write a loop." They test whether you can spot a hidden constraint that shrinks your search space. Smallest Palindromic Rearrangement is a great example: on the surface it looks like a permutation problem, and permutation problems have a bad reputation for exploding into factorial time. But the moment you notice the input has to stay a palindrome, half the string stops being a decision you make — it becomes a mirror of the other half.

This is worth learning well beyond the interview room. The same "reduce to the free half" idea shows up in nearest-valid-string problems, in DNA sequence repair algorithms, and generally anywhere you're asked to find the closest or smallest object inside a constrained space rather than an unconstrained one. Interviewers use this problem to check whether you reach for brute force out of habit, or whether you look for the constraint first.

Problem Overview

You're given a string that is guaranteed to already be a palindrome. Your job is to rearrange its letters — using every letter exactly once, no additions or removals — so that the result is:

1. Still a palindrome, and
2. The lexicographically smallest such palindrome possible.

"Lexicographically smallest" just means smallest in dictionary order — the way words are sorted in a dictionary, comparing letter by letter from the left.

Because the input is already a palindrome, you know something important going in: at most one letter in the whole string can have an odd count. Every other letter appears an even number of times. That's not a coincidence — it's a mathematical property of every palindrome, and it's the key that unlocks the whole problem.

Example

Take the string tacocat.

Count the letters: t:2, a:2, c:2, o:1.

Only o has an odd count, so o must sit in the exact center of the result — there's no other place it can go without breaking the palindrome property.

Everything else needs to be split into two equal, mirrored halves. Take the remaining letters t, t, a, a, c, c, halve each count (t:1, a:1, c:1), and sort them alphabetically to get the smallest possible left half: act.

Mirror that half around the center letter:

act + o + tca

Result: actotca.

Check it: is it a palindrome? Read it backwards — actotca reversed is actotca. Yes. Is it the smallest one possible? Since we built the left half using the smallest available letters in alphabetical order, nothing smaller could exist without changing which letters are available — and the multiset of letters is fixed.

Intuition

Here's how an experienced engineer approaches this, before writing a single line of code.

Start with the naive instinct: "generate every rearrangement, keep the ones that are palindromes, take the smallest." That's correct, but it's also wildly wasteful, and a good engineer's first move is to ask: what structure does this problem hand me for free?

The structure here is symmetry. A palindrome is completely defined by its first half (plus, if the length is odd, one center character). The second half isn't an independent choice — it's forced to be the mirror image of the first. That means the "real" problem isn't "arrange n characters into a palindrome." It's "arrange n/2 characters into the smallest possible string," which is a much easier problem you've solved before: sort them.

The only wrinkle is the middle character when the length is odd. Since the input is guaranteed to already be a palindrome, exactly one letter (or zero, if the length is even) has an odd count. That letter has nowhere else to go — it must be the center, because pairing it with anything else would break the even-count requirement for a valid palindrome.

So the recipe writes itself:

1. Count every letter.
2. Pull out the (at most one) odd-count letter as the center.
3. Halve every other count, sort those letters alphabetically — that's your left half.
4. Mirror the left half to build the right half.

No search. No candidates to filter. Just counting and sorting.

Brute Force Solution

Idea: Generate all n! permutations of the string, filter to the ones that are valid palindromes, and take the minimum.

Algorithm:

• Generate every permutation of the input characters.
• For each one, check if it equals its own reverse.
• Track the smallest palindromic permutation seen.

Advantages: Dead simple to reason about and impossible to get wrong — it's a literal restatement of the problem.

Disadvantages: Combinatorially explosive. Even a 7-character string like tacocat produces 5,040 permutations before filtering. At the problem's actual constraint (up to 100,000 characters), this approach doesn't just get slow — it becomes physically impossible to run, since n! for even moderately sized n exceeds the number of atoms in the observable universe.

Time complexity: O(n! · n) — factorial permutations, each requiring O(n) to check and compare. Space complexity: O(n! · n) if you materialize all candidates, or O(n) if you generate lazily and track only the best one so far — still useless at scale because of the time cost.

Optimal Solution

The optimal approach never generates a candidate string at all — it constructs the answer directly.

Step 1 — Count. Build a frequency map of every character using a Counter. This is a single O(n) pass.

Step 2 — Find the center. Scan the counts for the one with an odd value. Because the input is guaranteed to be a valid palindrome, there's at most one. If none exists, there's no center character (even-length palindrome).

Step 3 — Build the smallest half. For every letter, take count // 2 copies. Sort the resulting letters alphabetically — since earlier letters in the alphabet always produce a smaller string when placed earlier, sorting directly gives you the lexicographically smallest arrangement of that half-multiset.

Step 4 — Mirror. Concatenate: half + center + reversed(half).

A quick table for tacocat:

Letter	Count	Half count	Center?
t	2	1	no
a	2	1	no
c	2	1	no
o	1	0	yes

Sorted half: a, c, t → act. Final: act + o + tca = actotca.

Python Code

from collections import Counter


def smallest_palindromic_rearrangement(s: str) -> str:
    counts = Counter(s)

    center = ""
    half_letters = []

    for letter, count in counts.items():
        if count % 2 == 1:
            center = letter  # guaranteed at most one, since s is a palindrome
        half_letters.extend(letter * (count // 2))

    half_letters.sort()
    half = "".join(half_letters)

    return half + center + half[::-1]

Code Walkthrough

• Counter(s) builds the frequency map in one O(n) pass — no manual dictionary bookkeeping needed.
• The loop walks each distinct letter once. If its count is odd, it's stored as center. Since the input is guaranteed to be a palindrome, this branch fires at most once across the whole loop.
• half_letters.extend(letter * (count // 2)) adds count // 2 copies of the letter to the half-string's character pool. Integer division naturally drops the odd leftover character (which is already accounted for by center).
• half_letters.sort() arranges the pool alphabetically — this is the greedy step that guarantees lexicographic minimality.
• The return line assembles the answer: sorted half, then center, then the same half reversed to mirror it.

Dry Run

Input: tacocat

1. Counter("tacocat") → {'t': 2, 'a': 2, 'c': 2, 'o': 1}
2. Loop through the counts:
   • t: even → add "t" once to half_letters
   • a: even → add "a" once
   • c: even → add "c" once
   • o: odd → center = "o", add nothing (0 copies)
3. half_letters = ['t', 'a', 'c'] → sorted → ['a', 'c', 't']
4. half = "act"
5. Result: "act" + "o" + "tca" = "actotca"

Complexity Analysis

Time: O(n log n) — dominated by sorting the half-string, which has at most n/2 characters. Counting is O(n). Space: O(n) — for the counter and the half-string buffer.

This is correct because every step touches each character a bounded number of times: once to count it, at most once to place it in the half-string, and once during the sort comparison chain. Nothing revisits the full input more than a constant number of times, and the sort is the only super-linear step.

Alternative Solutions

You could skip building an explicit list and instead sort the distinct letters, then generate the half string letter-by-letter using string multiplication and "".join(). This is functionally identical and doesn't change the complexity class — it's a style preference, not a different algorithm. There isn't a fundamentally different approach worth comparing here, because once you accept the half-symmetry argument, sorting is provably optimal (see the exchange argument below) and nothing beats O(n log n) for that step.

Edge Cases

• Empty string: Counter is empty, loop doesn't fire, half is empty, center is empty. Returns "". Correct.
• Single character: One odd count, half stays empty, result is just that character. Correct.
• All identical characters (e.g., "aaaa"): One even count, half becomes "aa", no center, mirrors to "aaaa". The construction is a no-op on already-uniform input.
• Already the smallest arrangement: No special-casing needed — the algorithm always rebuilds from scratch and naturally reproduces the optimal string.
• Maximum length input (100,000 characters): O(n log n) sorting keeps this comfortably fast; no risk of timeout.

Common Mistakes

1. Assuming multiple odd counts are possible. The problem guarantees the input is already a palindrome, so this can't happen — but if you reuse this code on arbitrary strings, it silently picks the last odd-count letter it encounters as the center and drops the rest, which is a bug waiting to surface outside this problem's guarantees.
2. Sorting the full string instead of the half. This produces the wrong answer because it ignores the mirroring constraint entirely. 3Forgetting integer division drops the odd remainder. Using count / 2 instead of count // 2 in Python introduces a float and breaks string multiplication.
3. Rebuilding the right half independently instead of reversing the left half. This risks subtle bugs if the two halves ever drift out of sync — always derive the mirror from the same source.
4. Not sorting before mirroring. Building the half in insertion order instead of alphabetical order silently produces a valid palindrome that isn't the smallest one.

Interview Questions

• What if the input weren't guaranteed to be a valid palindrome — how would you detect that no rearrangement is possible?
• Can you prove that sorting the half-multiset actually produces the lexicographically smallest result? (Exchange argument: swapping any two out-of-order letters in the half can only make the result larger or equal, never smaller.)
• How would this change if you needed the largest palindromic rearrangement instead of the smallest?
• What's the complexity if you needed to generate the k-th smallest palindromic rearrangement instead of just the first?

Similar Problems

• Palindrome Permutation (LeetCode 266): Checks whether any palindrome permutation exists — the odd-count-parity check used here in isolation.
• Palindrome Permutation II (LeetCode 267): Asks for all distinct palindromic permutations, extending the half-construction idea into a full generation problem.
• Longest Palindromic Substring (LeetCode 5): A different palindrome family — searching within a string rather than constructing one from a multiset.
• Smallest Palindromic Rearrangement II: The natural follow-up (referenced in the video) — the harder variant where a simple mirror isn't enough on its own.

Key Takeaways

A constraint that reduces your degrees of freedom is a signal to reduce your algorithm's complexity class, not just optimize its constant factor. Recognizing that a palindrome is fully determined by its first half turns an n! search into an O(n log n) construction. The core interview skill being tested isn't palindrome trivia — it's the habit of asking "what does this constraint actually buy me?" before reaching for brute force.

Watch the Video

Prefer to see this walked through step by step, with the two quick quizzes included? Watch the full explanation here: {LINK}

About the Series

This breakdown is part of Fun with Learning Technology, a series that works through LeetCode Daily challenges by focusing on the reasoning behind each solution — not just the final code. Every video builds intuition first, so the pattern sticks with you well beyond the specific problem.

Call To Action

If this explanation helped the idea click, give the video a like on YouTube and subscribe so you don't miss the next problem in the series — tomorrow tackles the harder rearrangement variant where the mirror trick alone isn't enough. Subscribe to the Substack for the written breakdowns delivered straight to your inbox, drop a comment with your own approach or a question, and share this with anyone prepping for coding interviews.

---

half = []
mid = ""
for ch in sorted(cnt):
    c = cnt[ch]
    if c % 2:
        mid = ch
    half.append(ch * (c // 2))
half = "".join(half)