#3517

Medium

LeetCode Problem Workspace

Smallest Palindromic Rearrangement I

Build the smallest palindrome by sorting the left half counts and mirroring them around the optional middle character.

Problem Statement

You are given a lowercase string that is known to be rearrangeable into a palindrome, and in this problem it is already a palindrome. Your goal is to reorder its characters so the final palindrome is the smallest possible in lexicographic order, not just any valid palindromic permutation.

The key observation is that a palindrome is determined by its left half, an optional middle character, and the mirrored right half. For example, s = "z" stays "z" because a single character is already minimal, while inputs like "babab" and "daccad" become smaller by pushing smaller letters as far left as possible before mirroring them.

Examples

Example 1

Input: s = "z"

Output: "z"

A string of only one character is already the lexicographically smallest palindrome.

Example 2

Input: s = "babab"

Output: "abbba"

Rearranging "babab" → "abbba" gives the smallest lexicographic palindrome.

Example 3

Input: s = "daccad"

Output: "acddca"

Rearranging "daccad" → "acddca" gives the smallest lexicographic palindrome.

Constraints

1 <= s.length <= 105
s consists of lowercase English letters.
s is guaranteed to be palindromic.

Solution Approach

Count characters instead of generating rearrangements

Since the string is guaranteed to support a palindrome, you can count frequencies and focus on placement. Every pair of equal letters contributes one copy to the left half and one copy to the right half, while at most one leftover odd-count letter becomes the center.

Make the left half lexicographically smallest

Iterate letters from smallest to largest and append count[char] / 2 copies into the left half. This is the core String plus Sorting idea for this problem: once the left half is minimal, the mirrored palindrome is also minimal, because the first differing position between two candidate palindromes appears in that left half.

Mirror to finish the palindrome

After building the sorted left half, add the middle character if any count is odd, then append the reverse of the left half. This avoids the common failure mode of sorting the whole string and hoping it forms a palindrome, which does not control the mirrored structure correctly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

With lowercase English letters, counting takes O(n), scanning the alphabet is O(26), and constructing the result is O(n), so the total time is O(n) and the extra space is O(n) for the output plus O(26) for counts. If you generalize beyond a fixed alphabet and explicitly sort distinct characters, the pattern becomes O(n + k log k), where k is the number of unique letters.

What Interviewers Usually Probe

They hint that a palindrome can be viewed as two mirrored halves plus maybe one center character.
They care whether you know lexicographic order is decided by the earliest position, so the left half must be minimized first.
They want a counting-based construction, not brute-force permutation generation or repeated string resorting.

Common Pitfalls or Variants

Common pitfalls

Using all occurrences in sorted order without splitting pairs, which breaks the palindrome structure.
Choosing the middle character incorrectly when one frequency is odd, especially if you treat this as a validation problem instead of a construction problem.
Forgetting that the right half must be the reverse of the built left half, not another sorted copy in forward order.

Follow-up variants

Return any palindromic rearrangement instead of the lexicographically smallest one, which removes the need to prioritize smaller letters first.
Use a larger character set where you may need a hash map plus sorting of keys instead of fixed-size counting sort.
Ask for the largest palindromic rearrangement, which flips the ordering strategy on the left half from ascending to descending.

FAQ

What is the main trick in Smallest Palindromic Rearrangement I?

Treat the palindrome as left half, middle, and mirrored right half. Once you place the smallest possible letters into the left half in sorted order, the full palindrome is forced and is lexicographically minimal.

Why does sorting only the left half work?

Lexicographic comparison is decided at the first position where two strings differ. In any palindrome built from the same multiset, that first deciding position lies in the left half, so minimizing the left half automatically minimizes the whole answer.

Do I need to check whether a palindromic rearrangement exists?

No. This problem guarantees the input string is palindromic, so a valid palindromic permutation already exists. The task is purely to construct the smallest one.

How does Counting Sort fit this problem?

Because the string uses lowercase English letters, you can store frequencies in a 26-length array. That lets you build the left half in ascending letter order without a general-purpose sort, which keeps the solution linear.

What is the most common bug in this pattern?

A frequent mistake is building the right half incorrectly. The right side must be the reverse of the chosen left half, or the result either stops being a palindrome or stops being the smallest valid one.

terminal

Solution

Solution 1: Counting

We first count the occurrence of each character in the string and record it in a hash table or array $\textit{cnt}$. Since the string is a palindrome, the count of each character is either even, or there is exactly one character with an odd count.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        cnt = Counter(s)
        t = []
        ch = ""
        for c in ascii_lowercase:
            v = cnt[c] // 2
            t.append(c * v)
            cnt[c] -= v * 2
            if cnt[c] == 1:
                ch = c
        ans = "".join(t)
        ans = ans + ch + ans[::-1]
        return ans

Continue Practicing

#3545 minimum deletions for at most k distinct characters #3556 sum of largest prime substrings #3458 select k disjoint special substrings