Smallest Palindromic Rearrangement I — 🟡 Intermediate (2/3) — LeetCode Daily Python Solution (half the string, mirror the rest)

Introduction

Palindrome problems show up constantly in coding interviews, and for good reason — they force you to think about symmetry, which is a different muscle than the usual "iterate and track a variable" pattern. Smallest Palindromic Rearrangement I is a great example of a problem that looks like it needs heavy machinery (permutations, backtracking, sorting tricks) but actually collapses into something almost embarrassingly simple once you see the right observation.

What interviewers are really testing here isn't your ability to write a sort or a loop. It's whether you can spot redundant work. Half of this string is completely determined by the other half — that's the whole interview signal. If you internalize that pattern, you'll recognize it instantly the next time a problem hands you a symmetric structure, whether that's a palindrome, a mirrored tree, or a two-pointer scenario.

Problem Overview

You're given a string that is already a palindrome. Your job is to rearrange its letters — using every letter exactly once — so that the result is still a palindrome, but is the lexicographically smallest one possible.

In plain terms: same bag of letters, same "reads the same forwards and backwards" property, but arranged so it comes first alphabetically among all valid palindromic arrangements.

Because the input is guaranteed to already be a palindrome, you know something powerful about the letter counts before you even look at the string: every letter appears an even number of times, except possibly one letter, which appears an odd number of times and must sit dead center.

Example

Input: "babab" Output: "abbba"

Let's check the counts: b appears 3 times, a appears 2 times. Since b is odd, b becomes the center letter. The remaining letters are a, a, b, b, split evenly — half of them (a, b) form the left side, sorted smallest first.

Wait — sorted smallest first between a and b gives ab... but the actual output is abbba. Let's re-derive it directly from counts: half-counts are a: 1, b: 1. Sorting alphabetically gives the half-string ab. Mirroring around the center b gives ab + b + ba = abbba. That matches.

Another example: "tacocat"

Counts: t: 2, a: 2, c: 2, o: 1. Only o is odd, so o sits in the center. The remaining letters, each divided by two: t: 1, a: 1, c: 1. Sorted alphabetically, the half becomes act. Mirror it around o: act + o + tca = actotca.

Intuition

Here's the thought process an experienced engineer walks through, roughly in order:

First, notice the constraint that's easy to skim past: the input is already a palindrome. That's not flavor text — it's a guarantee about the shape of the letter-count distribution. In any palindrome, every character must be mirrored by an identical character on the other side, except possibly one character sitting alone in the exact middle (only possible when the string length is odd). So at most one letter can have an odd count.

Second, ask: if the right half of any palindrome is fully determined by the left half, why touch the right half at all? Every operation you'd perform on it — sorting, placing, comparing — is wasted work, because it always ends up being the mirror image of whatever you build on the left.

Third, think about what "smallest" means for a palindrome specifically. Lexicographic comparison looks left to right. Since the left half is read first, making the left half as small as possible, as early as possible, is the entire optimization. That means: take your smallest available letters and place them as far left as you can.

That naturally leads to the algorithm: tally the letters, pull out the (at most one) odd-count letter for the center, take half of every other letter's count, sort those halves alphabetically, and glue: half + middle + reverse(half).

Brute Force Solution

Idea: Generate every distinct permutation of the string, filter to the ones that read as palindromes, and pick the smallest one.

Algorithm:

1. Generate all unique permutations of the input string.
2. For each permutation, check if it equals its own reverse.
3. Among the palindromic permutations, return the alphabetically smallest.

Advantages: Dead simple to reason about, trivially correct, no clever insight required.

Disadvantages: Catastrophically slow. The number of permutations grows factorially with string length, and even after deduplicating repeated letters, you're still exploring a search space that's completely unnecessary given what we already know about palindrome structure.

Complexity: Time O(n!), space O(n!) to hold the permutations (or O(n) per permutation if generated lazily, but you're still paying O(n!) time). For a string of length 100,000, this isn't slow — it's uncomputable in the lifetime of the universe.

Optimal Solution

The Half and Mirror approach does one pass to count, one pass to build.

Step 1 — Tally. Walk the string once and count occurrences of each character using a hash map. Since the input is already a palindrome, at most one character will have an odd count.

Step 2 — Split. For every character, take count // 2 as its contribution to the left half. If a character has an odd count, remember it as the middle character (there's at most one).

Step 3 — Sort. Build the left half by walking characters in alphabetical order and repeating each one count // 2 times. Alphabetical order matters here — it's what guarantees the smallest possible left half, which guarantees the smallest possible whole string.

Step 4 — Mirror. Concatenate: left_half + middle_char (if any) + reversed(left_half).

A quick mental table for "tacocat":

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

Left half (alphabetical, repeated by half-count): a c t → "act". Middle: "o". Mirror: "act" + "o" + "tca" = "actotca".

Python Code

from collections import Counter


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

    middle = ""
    half_chars = []

    for char in sorted(counts):
        count = counts[char]
        if count % 2 == 1:
            middle = char  # at most one odd count, guaranteed by input being a palindrome
        half_chars.append(char * (count // 2))

    half = "".join(half_chars)
    return half + middle + half[::-1]

Code Walkthrough

• Counter(s) builds the letter tally in one linear pass — this is the "tally sheet" from the intuition section.
• sorted(counts) iterates the distinct characters in alphabetical order, which is what forces the smallest possible left half.
• Inside the loop, count % 2 == 1 catches the one letter (if any) with an odd count and stores it as middle. Because the input is guaranteed to already be a palindrome, this can happen at most once — no need to guard against multiple odd counts.
• half_chars.append(char * (count // 2)) builds up each letter's contribution to the left half, in the correct sorted position.
• half = "".join(half_chars) collapses the list into the final left-half string.
• The return statement mirrors it: half + middle + half[::-1] — left half, center (if any), and the left half reversed to form the right half.

Dry Run

Input: "babab"

1. Counter("babab") → {'b': 3, 'a': 2}
2. Sorted keys: ['a', 'b']
3. a: count 2, even → half_chars = ["a"]
4. b: count 3, odd → middle = "b", half_chars = ["a", "b"]
5. half = "ab"
6. Result: "ab" + "b" + "ba" = "abbba"

Matches the expected output.

Complexity Analysis

Time: O(n log k + n), where n is the string length and k is the alphabet size (at most 26 for lowercase English letters, so effectively a constant). Counting is O(n), sorting the distinct keys is O(k log k), and building the half/mirror strings is O(n). Overall this simplifies to O(n).

Space: O(n) for the output string and O(k) for the counts hash map, which is effectively O(1) additional space beyond the output since k is bounded by the alphabet size.

This is correct because every step touches each character a constant number of times — one count, one placement into the half, one mirrored copy — with no repeated or exponential work anywhere in the pipeline.

Alternative Solutions

You could sort the entire original string and then try to rearrange it into a palindrome shape directly, checking parity as you go. This works but is functionally identical to the Half and Mirror approach — it just does more bookkeeping to arrive at the same place. The count-and-mirror method is preferred because it separates concerns cleanly: counting logic never touches placement logic, which makes the code easier to verify and extend to a k-distinct-middle-character variant, which is exactly what the follow-up "Smallest Palindromic Rearrangement II" problem asks for.

Edge Cases

• Single character (e.g., "z"): half is empty, the whole string becomes the middle. Output: "z".
• All identical characters (e.g., "aaaa"): half is "aa", no middle, mirrors to "aaaa".
• Already smallest (e.g., "aba"): still rebuilt from scratch the same way — no special-casing needed, and the output equals the input.
• Two distinct letters, even length (e.g., "aabb" rearranged as a palindrome from "abba"): no odd counts, so no middle character; half is "ab", output "abba".
• Maximum length input (up to 100,000 characters): the linear algorithm handles this instantly, whereas brute force wouldn't finish.

Common Mistakes

1. Forgetting to pull out the odd-count letter separately before halving — this silently corrupts the palindrome property if you include it in the doubled half.
2. Sorting the wrong thing — sorting the full string instead of just the distinct characters used to build the half, which produces incorrect ordering when counts differ.
3. Assuming there can be more than one odd-count letter — this can't happen when the input is guaranteed to already be a palindrome, but it's an easy assumption to get wrong if you skip that guarantee.
4. Reversing the wrong half — mirroring the sorted half instead of building it once and reversing that exact string, which can introduce subtle bugs if the half is rebuilt from scratch for the right side.
5. Off-by-one errors with integer division — using count / 2 instead of count // 2 in Python, which produces a float and breaks string multiplication.

Interview Questions

• How would you handle this if the input string is not guaranteed to already be a palindrome?
• Can you produce not just the smallest, but the k-th smallest palindromic rearrangement?
• What if the string contains Unicode characters instead of just lowercase English letters — does your solution still hold?
• How would you extend this to find the largest palindromic rearrangement instead?
• Can you do this in-place, without allocating a new string for the output?

Similar Problems

• LeetCode 409 — Longest Palindrome: same core idea of counting letter parity, but focused on length instead of construction.
• LeetCode 680 — Valid Palindrome II: tests palindrome-checking with a single allowed deletion.
• LeetCode 5 — Longest Palindromic Substring: a different flavor of palindrome problem, focused on substrings rather than full rearrangements.
• LeetCode 3327 — Smallest Palindromic Rearrangement II: the direct sequel referenced in this video, extending the same trick to a harder variant.

Key Takeaways

Whenever a problem hands you a structure with built-in symmetry — a palindrome, a mirrored tree, a two-pointer array — look for the half you don't actually need to touch. Count once, sort the distinct symbols instead of the whole string, and let the mirror do the rest of the work for free. That single habit turns an exponential-looking problem into a linear one.

Watch the Video

For the full walkthrough with the "tacocat" pause-and-solve challenge, 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 intuition that lets you recognize the same pattern the next time it shows up in a different disguise.

Call To Action

If this breakdown helped the trick click, drop a like on the video and subscribe on YouTube — new daily solutions drop every day. For deeper write-ups like this one, subscribe to the Substack newsletter. And if you spotted a cleaner way to explain any part of this, drop it in the comments — sharing this with someone prepping for interviews helps more than you'd think.

---

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