3517. Smallest Palindromic Rearrangement I

MediumStringCounting SortSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a palindromic string s.

A string is a palindrome if it reads the same forwards and backwards. A permutation of a string is a rearrangement of all its characters. Your task is to find, among all possible palindromic permutations of s, the one that is lexicographically smallest.

A string a is lexicographically smaller than a string b (of the same length) if at the first position where they differ, the character in a comes earlier in the alphabet than the corresponding character in b.

Since s is already a palindrome, the count of each character in it is either even, or there is exactly one character with an odd count (which would sit in the middle of the palindrome).

Return the lexicographically smallest palindromic permutation of s.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

The problem counts character frequencies to construct the smallest palindromic permutation, placing half of each character in the first half and handling the center character.

Open in Flowchart

Intuition

Since s is already a palindrome, we know its characters can definitely be arranged into a palindrome. A palindrome is fully determined by its first half: once we fix the first half, the second half is just its mirror image, and possibly a single middle character if the length is odd.

To make the entire palindrome as small as possible lexicographically, we should make this first half as small as possible. The reason is that the first half drives the comparison: the earlier characters of the result string come from the first half, so minimizing the first half directly minimizes the whole palindrome.

How do we build the smallest possible first half? We simply place characters in alphabetical order. For each character, since a palindrome uses pairs of characters symmetrically, exactly half of its total count belongs to the first half. So if a character c appears cnt[c] times, then cnt[c] // 2 of them go into the first half. By processing characters from 'a' to 'z', we guarantee the first half is sorted in ascending order, which is the smallest arrangement possible.

If the string has odd length, exactly one character will have an odd count, leaving one leftover after forming pairs. That single leftover character must sit in the middle of the palindrome, since the middle is the only position not paired with another.

Finally, we assemble the answer by concatenating the first half t, the middle character ch (empty if the length is even), and the reverse of the first half t[::-1]. This produces a valid palindrome that is guaranteed to be the lexicographically smallest one.

Pattern Learn more about Sorting patterns.

Solution Approach

Solution 1: Counting

We first count the occurrence of each character in the string s using a hash table or array cnt. Since s is a palindrome, the count of each character is either even, or there is exactly one character with an odd count.

Next, we build the first half of the answer. Starting from the lexicographically smallest character, we iterate over each letter c from 'a' to 'z':

We compute v = cnt[c] // 2, which is the number of times c should appear in the first half.
We append c * v to a list t, gradually constructing the first half in ascending order.
We subtract v * 2 from cnt[c] to remove the paired characters. If cnt[c] is now 1, it means c is the character with an odd count, so we record it as the middle character ch.

After the loop, we join t into the string representing the first half. The final answer is formed by concatenating the first half, the middle character ch (which is an empty string if the length is even), and the reverse of the first half ans[::-1].

Example Walkthrough

Let's trace through the Counting solution using the small palindromic input s = "bcaacb".

Step 1: Count the characters

We tally each character's occurrences into cnt:

Character	Count
`a`	2
`b`	2
`c`	2

The string has length 6 (even), and every count is even — consistent with s being a palindrome. No middle character will be needed.

Step 2: Build the first half by iterating 'a' to 'z'

We process letters in alphabetical order to guarantee the smallest first half. For each letter c, we take v = cnt[c] // 2 copies into the first half t, then subtract v * 2 from cnt[c]:

c = 'a': v = 2 // 2 = 1, append "a" → t = ["a"], cnt['a'] = 0.
c = 'b': v = 2 // 2 = 1, append "b" → t = ["a", "b"], cnt['b'] = 0.
c = 'c': v = 2 // 2 = 1, append "c" → t = ["a", "b", "c"], cnt['c'] = 0.
c = 'd' … 'z': all counts are 0, nothing is appended.

No leftover count of 1 ever appears, so the middle character ch stays empty "".

Step 3: Assemble the palindrome

Join the first half: firstHalf = "abc".

Concatenate firstHalf + ch + reverse(firstHalf):

"abc" + "" + "cba" = "abccba"

Result: "abccba"

This is a valid palindrome (reads the same forwards and backwards) and is the lexicographically smallest among all palindromic permutations of "bcaacb". Any other arrangement, such as "bacab..." style orderings like "baccab", would start with a larger character (b instead of a) and therefore lose the comparison at the very first position.

A quick odd-length note: If we had s = "aba" instead, the counts would be a: 2, b: 1. Processing 'a' gives v = 1 → t = ["a"], cnt['a'] = 0. Processing 'b' gives v = 0, but cnt['b'] remains 1, so ch = "b" becomes the middle character. The answer assembles as "a" + "b" + "a" = "aba".

Solution Implementation

1from collections import Counter
2from string import ascii_lowercase
3
4
5class Solution:
6    def smallestPalindrome(self, s: str) -> str:
7        # Count the frequency of each character in the input string
8        char_count = Counter(s)
9
10        # Holds the left half of the resulting palindrome
11        left_half_parts = []
12        # Holds the single middle character (if any character has an odd count)
13        middle_char = ""
14
15        # Iterate through characters in alphabetical order to ensure the
16        # smallest lexicographical palindrome
17        for char in ascii_lowercase:
18            # Number of pairs that can be placed symmetrically on both sides
19            pair_count = char_count[char] // 2
20            left_half_parts.append(char * pair_count)
21
22            # Remove the characters already used in pairs
23            char_count[char] -= pair_count * 2
24
25            # If one character remains, it can be used as the middle character
26            if char_count[char] == 1:
27                middle_char = char
28
29        # Build the left half of the palindrome
30        left_half = "".join(left_half_parts)
31
32        # Combine left half, middle character, and the reversed left half
33        result = left_half + middle_char + left_half[::-1]
34
35        return result
36

1class Solution {
2    public String smallestPalindrome(String s) {
3        // Count the frequency of each lowercase letter in the input string.
4        int[] count = new int[26];
5        for (char c : s.toCharArray()) {
6            count[c - 'a']++;
7        }
8
9        // firstHalf will hold the first half of the resulting palindrome.
10        StringBuilder firstHalf = new StringBuilder();
11        // middle holds the single center character (if any letter has an odd count).
12        String middle = "";
13
14        // Iterate from 'a' to 'z' to build the lexicographically smallest result.
15        for (char c = 'a'; c <= 'z'; c++) {
16            int idx = c - 'a';
17
18            // Each pair of a character contributes one occurrence to the first half.
19            int pairs = count[idx] / 2;
20            if (pairs > 0) {
21                firstHalf.append(String.valueOf(c).repeat(pairs));
22            }
23
24            // Remove the characters already used in pairs.
25            count[idx] -= pairs * 2;
26
27            // If one character remains, it must be the center of the palindrome.
28            if (count[idx] == 1) {
29                middle = String.valueOf(c);
30            }
31        }
32
33        // Build the palindrome: firstHalf + middle + reverse(firstHalf).
34        String left = firstHalf.toString();
35        return left + middle + new StringBuilder(left).reverse();
36    }
37}
38

1class Solution {
2public:
3    string smallestPalindrome(string s) {
4        // Count the frequency of each lowercase letter in the input string.
5        vector<int> count(26, 0);
6        for (char c : s) {
7            count[c - 'a']++;
8        }
9
10        // Build the first half of the palindrome.
11        // Iterating from 'a' to 'z' guarantees lexicographically smallest order.
12        string firstHalf = "";
13        // Holds the single middle character (for odd-length palindromes), if any.
14        string middle = "";
15        for (char c = 'a'; c <= 'z'; ++c) {
16            // Each pair of identical characters contributes one char to each half.
17            int pairs = count[c - 'a'] / 2;
18            if (pairs > 0) {
19                firstHalf.append(pairs, c);
20            }
21            // Remove the used pairs; what remains is 0 or 1.
22            count[c - 'a'] -= pairs * 2;
23            // If one character is left over, it can serve as the middle character.
24            if (count[c - 'a'] == 1) {
25                middle = string(1, c);
26            }
27        }
28
29        // Construct the palindrome: firstHalf + middle + reversed(firstHalf).
30        string answer = firstHalf;
31        answer += middle;
32        string secondHalf = firstHalf;
33        reverse(secondHalf.begin(), secondHalf.end());
34        answer += secondHalf;
35
36        return answer;
37    }
38};
39

1/**
2 * Builds the lexicographically smallest palindrome that can be formed
3 * by rearranging all characters of the given string.
4 *
5 * Assumes the input is guaranteed to be rearrangeable into a palindrome
6 * (i.e., at most one character has an odd frequency).
7 *
8 * @param s - The input string consisting of lowercase English letters.
9 * @returns The smallest palindrome formed from the characters of `s`.
10 */
11function smallestPalindrome(s: string): string {
12    const asciiLowercase = 'abcdefghijklmnopqrstuvwxyz';
13
14    // Count the occurrences of each lowercase letter.
15    const count = new Array<number>(26).fill(0);
16    for (const char of s) {
17        count[char.charCodeAt(0) - 97]++;
18    }
19
20    // Build the first half of the palindrome in ascending (smallest) order.
21    const halfParts: string[] = [];
22    // Holds the single middle character if any letter has an odd frequency.
23    let middleChar = '';
24
25    for (let i = 0; i < 26; i++) {
26        const currentChar = asciiLowercase[i];
27
28        // Each pair contributes one character to the first half.
29        const pairCount = Math.floor(count[i] / 2);
30        halfParts.push(currentChar.repeat(pairCount));
31
32        // Remove the used pairs; a leftover of 1 marks the middle character.
33        count[i] -= pairCount * 2;
34        if (count[i] === 1) {
35            middleChar = currentChar;
36        }
37    }
38
39    // Concatenate the first half, the optional middle character, and the
40    // reversed first half to form the complete palindrome.
41    const firstHalf = halfParts.join('');
42    const secondHalf = firstHalf.split('').reverse().join('');
43
44    return firstHalf + middleChar + secondHalf;
45}
46

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s. Building the Counter takes O(n) time. The loop over ascii_lowercase runs a constant 26 times, but the total length of strings appended to t (via c * v) sums to at most n / 2, so constructing the half-palindrome with "".join(t) costs O(n). Reversing ans[::-1] and concatenating also take O(n). Therefore, the overall time complexity is O(n).
Space Complexity: O(|\Sigma|), where |\Sigma| is the size of the character set, which is 26 in this problem. The Counter uses O(|\Sigma|) space since there are at most 26 distinct lowercase letters. Note that although t and the final answer ans hold O(n) characters, these are part of the required output rather than auxiliary space, so the extra space is dominated by the counter, giving O(|\Sigma|).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Reversing the wrong portion when building the right half

A frequent mistake is reversing the middle-inclusive part or even the entire result instead of just the left half. For example, writing result = left_half + middle_char + (left_half + middle_char)[::-1] would duplicate the middle character, producing a string that is no longer a valid palindrome (and is the wrong length).

Wrong:

# This duplicates the middle character!
result = left_half + middle_char + (left_half + middle_char)[::-1]

Correct:

# Only reverse the left half; the middle stays exactly once.
result = left_half + middle_char + left_half[::-1]

The middle character must appear exactly once in the center, so only left_half should be mirrored.

Pitfall 2: Assuming there can be more than one odd-count character

Some implementations try to "fix" multiple odd-count characters or fail to handle the middle character at all. Because the problem guarantees s is already a palindrome, at most one character can have an odd count. Relying on this guarantee is correct, but the code must still capture that single middle character properly.

A subtle bug arises if you reset or overwrite middle_char incorrectly. Since only one character can be odd, the assignment inside the loop is safe—but if you accidentally append the middle character into left_half_parts too, the result becomes malformed.

Wrong:

for char in ascii_lowercase:
    pair_count = char_count[char] // 2
    left_half_parts.append(char * pair_count)
    char_count[char] -= pair_count * 2
    if char_count[char] == 1:
        middle_char = char
        left_half_parts.append(char)  # BUG: adds middle into the half

Correct:

for char in ascii_lowercase:
    pair_count = char_count[char] // 2
    left_half_parts.append(char * pair_count)
    char_count[char] -= pair_count * 2
    if char_count[char] == 1:
        middle_char = char  # Only record it; do NOT append to the half

Pitfall 3: Iterating over the string instead of the alphabet

To guarantee lexicographically smallest order, you must iterate from 'a' to 'z'. A common error is iterating over set(s) or the original string order, which does not produce a sorted left half.

Wrong:

for char in set(s):       # Unordered iteration!
    pair_count = char_count[char] // 2
    left_half_parts.append(char * pair_count)

Correct:

for char in ascii_lowercase:  # Guaranteed 'a' -> 'z' order
    pair_count = char_count[char] // 2
    left_half_parts.append(char * pair_count)

Sorting the characters explicitly (or iterating over ascii_lowercase) is what ensures the smallest possible arrangement, since placing smaller characters earlier in the left half minimizes the string at the first differing position.

Pitfall 4: Off-by-one with odd counts using integer division

When a character has an odd count, char_count[char] // 2 correctly leaves a remainder of 1. Forgetting to subtract pair_count * 2 (and instead subtracting pair_count) would leave a wrong residual, breaking the == 1 middle-character check.

Wrong:

char_count[char] -= pair_count  # Leaves too many characters behind

Correct:

char_count[char] -= pair_count * 2  # Removes both halves of each pair

This keeps the residual at 0 (even count) or 1 (the single odd character), making the middle-character detection reliable.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

3517. Smallest Palindromic Rearrangement I

Problem Description

How We Pick the Algorithm

Why Hash Table / Counting?

Intuition

Solution Approach

Solution 1: Counting

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Reversing the wrong portion when building the right half

Pitfall 2: Assuming there can be more than one odd-count character

Pitfall 3: Iterating over the string instead of the alphabet

Pitfall 4: Off-by-one with odd counts using integer division

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings