LeetCode Problem 3517

Difficulty: 🟡 Medium
Topics: String, Sorting, Counting Sort

Solution

Problem Understanding

The problem asks us to take a palindromic string s and return its lexicographically smallest palindromic permutation. In other words, we need to rearrange the characters of s into a palindrome that is the smallest possible if you were to compare it alphabetically with all other palindromic arrangements.

The input string s is guaranteed to already be a palindrome, meaning it reads the same forwards and backwards. The output must also be a palindrome, but we can reorder characters to minimize its lexicographic order. Lexicographic order means the usual dictionary order; for example, "aab" comes before "aba".

The constraints indicate that s can be quite large (up to 105 characters) and only contains lowercase English letters (a-z). The fact that s is guaranteed to be palindromic simplifies our solution because a valid rearrangement must have at most one character with an odd frequency. This is a property of palindromes: each character must appear an even number of times, except possibly one in the middle.

Important edge cases include: strings of length 1, strings where all characters are the same, and strings that already appear to be lexicographically minimal.

Approaches

Brute Force Approach

A brute force approach would generate all permutations of s and filter only the ones that are palindromes. Then we could sort them lexicographically and pick the first one. This would give the correct answer but is computationally infeasible for large strings because the number of permutations is factorial in the length of the string, which exceeds 105!.

Optimal Approach

The key insight is that for a string that is already palindromic, we do not need to consider all permutations. Instead, we can count the frequency of each character, place half of each character in order for the first half of the palindrome, optionally put a single character with odd frequency in the middle, and then mirror the first half for the second half of the palindrome. Sorting the first half in lexicographic order guarantees the final palindrome is the smallest lexicographically. This approach reduces the problem to counting and sorting, which is efficient and scales linearly with respect to the alphabet size (26 letters).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Generates all permutations and filters palindromes, not feasible for large n
Optimal	O(n + k log k) ~ O(n)	O(k) ~ O(26)	Count characters, sort half, mirror, efficient and straightforward

Algorithm Walkthrough

1. Count Character Frequencies: Create a frequency map of all characters in the string s. Since s only contains lowercase letters, we can use a fixed array of size 26 for efficiency.
2. Split Characters into Halves: For each character, calculate how many times it should appear in the first half of the palindrome. This is count // 2. Keep track of any character with an odd frequency as a potential middle character.
3. Sort the First Half: Sort the characters selected for the first half in lexicographical order. This guarantees that the resulting palindrome will be the smallest possible.
4. Construct the Full Palindrome: Concatenate the first half, the middle character (if one exists), and the reverse of the first half to form the complete palindrome.
5. Return the Result: The constructed string is the lexicographically smallest palindromic permutation of s.

Why it works: By taking half of each character and arranging it in sorted order, we ensure the lexicographically smallest prefix. The mirrored second half preserves the palindrome property. Any odd-count character must go in the middle; placing it there does not affect lexicographical order because it is surrounded by symmetric halves. The problem gives a string s that is already guaranteed to be a palindrome, and asks us to construct the lexicographically smallest palindromic permutation of that string.

In other words, we are allowed to rearrange the characters of s, but the result must still be a palindrome, and among all such valid palindromic rearrangements, we must return the one that is smallest in lexicographic order.

The input string consists only of lowercase English letters and has length up to 100,000. Since the string is guaranteed to be a palindrome, we also implicitly know that at most one character can have an odd frequency count, and all others must appear an even number of times.

The key output requirement is not just any palindrome, but the lexicographically smallest one, meaning that when comparing from left to right, the earliest position where two candidates differ determines which is smaller.

Important edge cases include strings of length 1, strings where all characters are identical, and strings where multiple valid palindromic permutations exist due to repeated characters. The guarantee that the input is already a palindrome removes invalid cases such as impossible frequency distributions.

Approaches

The brute-force approach would generate all permutations of the string, filter those that are palindromes, and then select the lexicographically smallest one. While conceptually straightforward, this is infeasible because generating permutations has factorial complexity, and even checking each permutation for palindrome validity would be too slow for n = 100,000.

The key insight is that we do not actually need to permute arbitrarily. A palindrome is fully determined by its first half and an optional middle character. Therefore, the problem reduces to arranging the first half in lexicographically smallest order, then mirroring it.

Since we want the smallest lexicographic palindrome, the first half itself must be the smallest lexicographic arrangement of available characters. That means we simply count character frequencies, construct half of the palindrome using sorted characters in increasing order, place the odd-count character (if any) in the middle, and mirror the half.

This reduces the problem from permutation generation to frequency counting and sorting, which is optimal for the constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * n)	O(n!)	Generate all permutations, filter palindromes, extremely slow
Optimal	O(n + 26 log 26) ≈ O(n)	O(n)	Count frequencies and build half palindrome greedily

Algorithm Walkthrough

The optimal solution is based on frequency counting and constructive building of the palindrome.

1. First, compute the frequency of each character in the string. This is necessary because a palindrome is symmetric, so we only need to know how many of each character we have, not their positions.
2. Identify the character (if any) that has an odd frequency count. Since the string is guaranteed to be a palindrome, there can be at most one such character. This character will be placed in the center of the final palindrome.
3. For every character from 'a' to 'z', take half of its frequency (integer division by 2). These characters will form the left half of the palindrome.
4. Construct the left half by appending characters in lexicographically increasing order, repeating each character the computed number of times. This greedy ordering ensures the left half is the smallest possible arrangement.
5. Construct the right half by reversing the left half. This ensures the full string is a valid palindrome.
6. If a middle character exists (odd frequency), insert it between the two halves.

The ordering constraint is fully handled by always filling the left half in sorted order, which guarantees lexicographic minimality.

Why it works

The correctness comes from the fact that a palindrome is uniquely determined by its first half and middle character. Since lexicographic order is determined from left to right, minimizing the left half automatically minimizes the entire string. Any deviation from sorted order in the left half would immediately create a larger lexicographic result, so the greedy construction is optimal.

Python Solution

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        from collections import Counter
        
        count = Counter(s)
        first_half = []
        middle_char = ''
        
        for ch in sorted(count.keys()):
            times = count[ch] // 2
            first_half.append(ch * times)
            if count[ch] % 2 == 1:
                middle_char = ch
        
        first_half_str = ''.join(first_half)
        return first_half_str + middle_char + first_half_str[::-1]

Implementation Walkthrough: We use Counter to tally each character's occurrences. For each character in sorted order, we add half of its occurrences to the first_half list. If the character has an odd count, we designate it as the middle character. Finally, we concatenate the first half, the middle character, and the reversed first half to get the smallest palindrome. freq = [0] * 26

    for ch in s:
        freq[ord(ch) - ord('a')] += 1
    
    middle = ""
    left_half = []
    
    for i in range(26):
        if freq[i] % 2 == 1:
            middle = chr(i + ord('a'))
        left_half.append(chr(i + ord('a')) * (freq[i] // 2))
    
    left = "".join(left_half)
    right = left[::-1]
    
    return left + middle + right

The implementation begins by building a fixed-size frequency array for the 26 lowercase letters. It then determines the middle character by checking for an odd count. The left half is constructed in sorted order by iterating from `'a'` to `'z'` and appending half the frequency of each character. Finally, the right half is created by reversing the left half, and both halves are combined with the middle character if needed.

## Go Solution

```go
import "sort"
import "strings"

func smallestPalindrome(s string) string {
    count := [26]int{}
    for _, ch := range s {
        count[ch-'a']++
    }

    var firstHalf []string
    middleChar := ""
    
    for i := 0; i < 26; i++ {
        times := count[i] / 2
        if times > 0 {
            firstHalf = append(firstHalf, strings.Repeat(string('a'+i), times))
        }
        if count[i]%2 == 1 {
            middleChar = string('a' + i)
        }
    }

    firstHalfStr := strings.Join(firstHalf, "")
    secondHalf := reverseString(firstHalfStr)
    return firstHalfStr + middleChar + secondHalf
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

Go-specific Notes: We use a fixed-size array of 26 integers for counts, which is more efficient than a map. String concatenation is done via strings.Join for the first half. We handle reversal using a helper function that swaps runes to ensure Unicode safety.

Worked Examples

Example 1: s = "z"

Step	first_half	middle_char	palindrome
Count	{'z': 1}
Half	''	'z'	''
Result	''	'z'	'z'

Example 2: s = "babab"

Step	first_half	middle_char	palindrome
Count	{'a':2, 'b':3}
Half	'ab'	'b'	'ab'
Result	'ab'	'b'	'abbba'

Example 3: s = "daccad"

Step	first_half	middle_char	palindrome
Count	{'a':2, 'c':2, 'd':2}
Half	'acd'	''	'acd'
Result	'acd'	''	'acddca'
func smallestPalindrome(s string) string {
freq := make([]int, 26)

for _, ch := range s {
    freq[ch-'a']++
}

middle := byte(0)
left := make([]byte, 0, len(s)/2)

for i := 0; i < 26; i++ {
    if freq[i]%2 == 1 {
        middle = byte(i + 'a')
    }
    for j := 0; j < freq[i]/2; j++ {
        left = append(left, byte(i+'a'))
    }
}

n := len(left)
result := make([]byte, 0, len(s))

result = append(result, left...)

if middle != 0 {
    result = append(result, middle)
}

for i := n - 1; i >= 0; i-- {
    result = append(result, left[i])
}

return string(result)

}

In Go, we explicitly manage byte slices instead of strings for efficiency. The frequency array is built the same way. The left half is constructed as a byte slice with preallocation. The middle character is stored as a byte, with zero used as a sentinel for “no middle character.” The final palindrome is built by appending the left half, then the middle character if it exists, then the reversed left half.

## Worked Examples

### Example 1: s = "z"

We compute frequencies: `z:1`. The middle becomes `'z'`, and the left half is empty.

| Step | Left Half | Middle | Right Half | Result |
| --- | --- | --- | --- | --- |
| Count | "" | "z" | "" | "z" |

Final output is `"z"`.

### Example 2: s = "babab"

Frequencies: `a:2, b:3`. Half counts are `a:1, b:1`.

We build left half in sorted order: `"ab"`.

| Step | Left Half | Middle | Right Half | Result |
| --- | --- | --- | --- | --- |
| Build | "ab" | "b" | "" | "ab" |
| Mirror | "ab" | "b" | "ba" | "abbba" |

Final result is `"abbba"`.

### Example 3: s = "daccad"

Frequencies: `a:2, c:2, d:2`. No odd frequency, so no middle.

Half counts: `a:1, c:1, d:1`.

Left half is built in sorted order: `"acd"`.

| Step | Left Half | Middle | Right Half | Result |
| --- | --- | --- | --- | --- |
| Build | "acd" | "" | "" | "acd" |
| Mirror | "acd" | "" | "dca" | "acddca" |

Final output is `"acddca"`.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n + k log k) ~ O(n) | Counting characters is O(n), sorting up to 26 letters is negligible |
| Space | O(k) ~ O(26) | Fixed-size array for counts and half construction |

The overall algorithm scales linearly with string length. Sorting the 26 letters is effectively constant time.
| Time | O(n) | Counting characters is O(n), building the result is O(26 + n) which simplifies to O(n) |
| Space | O(n) | We store the left half and final result string proportional to input size |

The algorithm is linear because it avoids sorting the entire string and instead relies on fixed-size frequency counting over the alphabet.

## Test Cases

Provided examples

assert Solution().smallestPalindrome("z") == "z" # single character assert Solution().smallestPalindrome("babab") == "abbba" # odd length with middle assert Solution().smallestPalindrome("daccad") == "acddca" # even length

Edge cases

assert Solution().smallestPalindrome("aaaa") == "aaaa" # all same characters assert Solution().smallestPalindrome("abcba") == "abcba" # already minimal assert Solution().smallestPalindrome("edcbaabcde") == "aabbcdcbaa" # longer string assert Solution().smallestPalindrome("x") == "x" # minimal single char assert Solution().smallestPalindrome("z") == "z" # single character assert Solution().smallestPalindrome("babab") == "abbba" # example case assert Solution().smallestPalindrome("daccad") == "acddca" # example case assert Solution().smallestPalindrome("aa") == "aa" # all identical even length assert Solution().smallestPalindrome("aaa") == "aaa" # all identical odd length assert Solution().smallestPalindrome("aabb") == "abba" # simple rearrangement assert Solution().smallestPalindrome("civic") == "civic" # already smallest palindrome assert Solution().smallestPalindrome("aaabbbb") == "aabbbba" # multiple valid permutations

| Test | Why |
| --- | --- |
| "z" | Single character, minimal palindrome |
| "babab" | Odd length with middle character |
| "daccad" | Even length, needs sorting for minimal palindrome |
| "aaaa" | All same characters |
| "abcba" | Already minimal |
| "edcbaabcde" | Longer palindrome requiring rearrangement |
| "x" | Minimal edge case, single character |

## Edge Cases

**Single-character strings**: These are already palindromes and lexicographically minimal. The algorithm correctly returns the input.

**Strings where all characters are the same**: The half-construction and mirroring approach naturally preserves the string. Sorting does not change it.

**Strings with multiple possible middle characters**: The problem guarantees a valid palindrome input, so at most one character will have an odd frequency. The algorithm correctly selects that character as the middle. No additional logic is needed.

**Already lexicographically minimal**: If the input is already minimal, sorting and mirroring will not alter the
| "z" | minimal length input |
| "babab" | standard odd-length palindrome |
| "daccad" | even-length with rearrangement |
| "aa" | uniform characters |
| "aaa" | odd uniform characters |
| "aabb" | multiple valid permutations |
| "civic" | already optimal arrangement |
| "aaabbbb" | mixed frequency balancing |

## Edge Cases

One important edge case is a single-character string. Since no rearrangement is possible, the function must immediately return the same character, and the algorithm naturally handles this because the frequency array produces a single odd character and an empty left half.

Another edge case is when all characters are identical. In this case, the frequency split still produces a valid palindrome, but the left half may be empty or fully symmetric depending on parity. The implementation handles this correctly because integer division ensures symmetry automatically.

A third edge case is when multiple characters have valid frequencies but only one can appear in the center. The algorithm ensures correctness by always selecting the last odd-frequency character encountered in sorted order, which is safe because the input is guaranteed to already be a palindrome, meaning at most one such character exists.