LeetCode 3518 - Smallest Palindromic Rearrangement II

We are given a string s that is guaranteed to already be a palindrome. We may rearrange its characters, but the final rearranged string must also be a palindrome.

leetcodehardhash-tablemathstringcombinatoricscounting

LeetCode Problem 3518

Difficulty: 🔴 Hard
Topics: Hash Table, Math, String, Combinatorics, Counting

Solution

Problem Understanding

We are given a string s that is guaranteed to already be a palindrome. We may rearrange its characters, but the final rearranged string must also be a palindrome.

Among all distinct palindromic permutations that can be formed from the characters of s, we must return the k-th lexicographically smallest one. If fewer than k distinct palindromic permutations exist, we return an empty string.

A key observation is that a palindrome is completely determined by its first half. Once we choose the left half, the right half is forced to be its mirror image. If the palindrome length is odd, there is also exactly one middle character whose count is odd.

For example:

  • "abba" has character counts {a:2, b:2}.
  • The left half must contain one a and one b.
  • Possible left halves are "ab" and "ba".
  • These generate palindromes "abba" and "baab".

The constraints are important:

  • s.length <= 10^4
  • Only lowercase English letters appear.
  • k <= 10^6

A brute force generation of all palindromic permutations is impossible because the number of permutations can be enormous. We need a combinatorial counting approach that can determine how many palindromes begin with a particular prefix without explicitly generating them.

Important edge cases include:

  • A string with only one possible palindromic rearrangement.
  • Cases where k exceeds the total number of palindromic permutations.
  • Odd length palindromes with a middle character.
  • Very large strings where direct factorial computation would be expensive.
  • Situations where the number of palindromic permutations is much larger than 10^6, requiring careful count capping.

Approaches

Brute Force

A naive solution would generate every distinct palindromic permutation, sort them lexicographically, and return the k-th one.

Since every palindrome is determined by its first half, we could generate all distinct permutations of the half-string, construct the corresponding palindrome for each permutation, sort them, and select the answer.

This approach is correct because it explicitly enumerates every valid palindrome exactly once. However, it quickly becomes infeasible. Even a half-string of length 20 may have millions or billions of distinct permutations.

Therefore, brute force cannot handle strings of length up to 10^4.

Key Insight

A palindrome is determined entirely by:

  • The multiset of characters in its left half.
  • The optional middle character.

Let:

  • halfCount[c] = freq[c] / 2
  • m = sum(halfCount)

The number of distinct palindromic permutations equals the number of distinct permutations of the half-string:

$$\frac{m!}{\prod_c (halfCount[c]!)}$$

Instead of generating all permutations, we construct the answer greedily from left to right.

At each position of the left half:

  1. Try characters in lexicographic order.
  2. Tentatively place a character.
  3. Count how many valid half-strings can be formed afterward.
  4. If that count is at least k, we keep that character.
  5. Otherwise, we skip all those permutations by subtracting the count from k and try the next character.

This is exactly the standard "k-th lexicographic permutation" idea, combined with multinomial counting.

The challenge is efficiently computing the number of remaining permutations after each choice.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Generates all palindromic permutations
Optimal O(n · 26) O(n) Greedy construction with multinomial counting

Algorithm Walkthrough

Step 1: Count character frequencies

Compute the frequency of each character in s.

Because s is guaranteed to be a palindrome, at most one character has an odd count.

Step 2: Build half-counts

For each character:

$$halfCount[c] = \frac{freq[c]}{2}$$

The palindrome's left half contains exactly these characters.

Also record the middle character if one exists.

Step 3: Compute total permutations

Let:

$$m = \sum halfCount[c]$$

The total number of distinct left-half permutations is:

$$\frac{m!}{\prod_c halfCount[c]!}$$

If this number is smaller than k, return an empty string immediately.

Since k ≤ 10^6, we only care whether counts exceed 10^6. We can safely cap all counts at 10^6 + 1.

Step 4: Maintain the current permutation count

Suppose the current remaining counts are:

$$c_1,c_2,\ldots,c_t$$

and the total remaining positions are:

$$rem$$

Let:

$$ways = \frac{rem!}{\prod_i c_i!}$$

This represents the number of valid half-strings that can be formed from the current state.

Step 5: Choose characters greedily

For each position in the half-string:

  1. Iterate through characters 'a' to 'z'.
  2. Skip characters whose count is zero.
  3. Suppose we place character x.

The number of permutations beginning with this choice is:

$$ways_x = ways \cdot \frac{count_x}{rem}$$

This follows directly from multinomial coefficients.

  1. If k > ways_x, then all such permutations come before the desired answer.
  • Set k -= ways_x.
  • Try the next character.
  1. Otherwise:
  • Append x.
  • Update counts.
  • Set ways = ways_x.
  • Move to the next position.

Step 6: Construct the palindrome

After the left half is determined:

  • Right half = reverse(left half)
  • Middle character = odd-frequency character if one exists

Return:

$$left + middle + reverse(left)$$

Why it works

At every position, lexicographic ordering groups all palindromes sharing the same prefix into a contiguous block. The multinomial coefficient gives the exact size of each block. By comparing k against those block sizes, we can determine which block contains the desired palindrome. Repeating this process position by position uniquely identifies the k-th lexicographic palindromic permutation.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def smallestPalindrome(self, s: str, k: int) -> str:
        LIMIT = 1_000_001

        freq = Counter(s)

        half = [0] * 26
        middle = ""

        for ch, cnt in freq.items():
            idx = ord(ch) - ord("a")
            half[idx] = cnt // 2
            if cnt % 2:
                middle = ch

        m = sum(half)

        ways = 1
        remaining = 0

        for cnt in half:
            for i in range(1, cnt + 1):
                ways = ways * (remaining + i) // i
                if ways > LIMIT:
                    ways = LIMIT
            remaining += cnt

        if ways < k:
            return ""

        left = []
        rem = m

        for _ in range(m):
            for c in range(26):
                if half[c] == 0:
                    continue

                block = ways * half[c] // rem
                if block > LIMIT:
                    block = LIMIT

                if k > block:
                    k -= block
                    continue

                left.append(chr(ord("a") + c))
                ways = block
                half[c] -= 1
                rem -= 1
                break

        left_half = "".join(left)
        return left_half + middle + left_half[::-1]

The implementation begins by counting character frequencies and extracting the counts needed for the left half of the palindrome. The middle character is recorded separately when an odd frequency exists.

The multinomial coefficient is computed incrementally. Rather than evaluating huge factorials directly, we build the value using the standard combinatorial identity for inserting each character group into the growing multiset. Since only comparisons with k matter, every value is capped at 1,000,001.

The greedy construction then proceeds position by position. For every candidate character, the number of palindromic permutations beginning with that choice is derived from the current multinomial count using the relation:

$$ways_x = ways \cdot \frac{count_x}{rem}$$

If the desired rank lies beyond that block, we skip it. Otherwise we commit to the character and continue.

Finally, the palindrome is reconstructed from the chosen left half, optional middle character, and mirrored right half.

Go Solution

func smallestPalindrome(s string, k int) string {
	const LIMIT int64 = 1000001

	freq := make([]int, 26)
	for _, ch := range s {
		freq[ch-'a']++
	}

	half := make([]int, 26)
	middle := byte(0)

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

	m := 0
	for _, v := range half {
		m += v
	}

	var ways int64 = 1
	remaining := 0

	for _, cnt := range half {
		for i := 1; i <= cnt; i++ {
			ways = ways * int64(remaining+i) / int64(i)
			if ways > LIMIT {
				ways = LIMIT
			}
		}
		remaining += cnt
	}

	if ways < int64(k) {
		return ""
	}

	left := make([]byte, 0, m)
	rem := m
	rank := int64(k)

	for pos := 0; pos < m; pos++ {
		for c := 0; c < 26; c++ {
			if half[c] == 0 {
				continue
			}

			block := ways * int64(half[c]) / int64(rem)
			if block > LIMIT {
				block = LIMIT
			}

			if rank > block {
				rank -= block
				continue
			}

			left = append(left, byte('a'+c))
			ways = block
			half[c]--
			rem--
			break
		}
	}

	n := len(left)
	result := make([]byte, 0, 2*n+1)

	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)
}

The Go implementation follows exactly the same mathematical approach. The main difference is the use of int64 for combinatorial counts. Since counts are capped at 1,000,001, overflow is not a concern. Slices are used for efficient construction of both the left half and the final palindrome.

Worked Examples

Example 1

Input

s = "abba"
k = 2

Frequency Table

Character Count
a 2
b 2

Half Counts

Character Half Count
a 1
b 1

Left-half length:

Variable Value
m 2

Total permutations:

$$\frac{2!}{1!\cdot1!}=2$$

Position 0

Candidate Block Size
a 1
b 1

Since k = 2, skip the a block.

Variable Value
k 1
chosen b

Position 1

Only a remains.

Left half:

ba

Palindrome:

baab

Output:

"baab"

Example 2

Input

s = "aa"
k = 2

Half counts:

Character Half Count
a 1

Total permutations:

$$1$$

Since:

1 < 2

return:

""

Example 3

Input

s = "bacab"
k = 1

Frequency table:

Character Count
a 2
b 2
c 1

Half counts:

Character Half Count
a 1
b 1

Middle character:

c

Total permutations:

$$2$$

Position 0

Candidate Block Size
a 1
b 1

Since k = 1, choose a.

Position 1

Only b remains.

Left half:

ab

Middle:

c

Palindrome:

abcba

Output:

"abcba"

Complexity Analysis

Measure Complexity Explanation
Time O(n + 26·n) Frequency counting plus greedy construction of half-string
Space O(n) Output string and half-count storage

The alphabet size is fixed at 26. During construction, each position of the half-string examines at most 26 candidate characters. Since the half length is at most n/2, the overall complexity is linear in the input size, up to a small constant factor.

Test Cases

sol = Solution()

assert sol.smallestPalindrome("abba", 2) == "baab"  # sample 1
assert sol.smallestPalindrome("aa", 2) == ""  # sample 2
assert sol.smallestPalindrome("bacab", 1) == "abcba"  # sample 3

assert sol.smallestPalindrome("a", 1) == "a"  # single character
assert sol.smallestPalindrome("a", 2) == ""  # rank too large

assert sol.smallestPalindrome("aaaa", 1) == "aaaa"  # only one arrangement
assert sol.smallestPalindrome("aaaa", 2) == ""  # rank exceeds count

assert sol.smallestPalindrome("aabbaa", 1) == "aabbaa"  # smallest palindrome
assert sol.smallestPalindrome("aabbaa", 2) == "abaaba"  # second palindrome
assert sol.smallestPalindrome("aabbaa", 3) == "baaaab"  # third palindrome
assert sol.smallestPalindrome("aabbaa", 4) == ""  # exceeds total

assert sol.smallestPalindrome("aaaabbbb", 1) == "aabbbbaa"  # first lexicographic
assert sol.smallestPalindrome("aaaabbbb", 6) == "bbaaaabb"  # last permutation

assert sol.smallestPalindrome("abcddcba", 1) == "abcddcba"  # many distinct choices

assert sol.smallestPalindrome("racecar".replace("r", "r"), 1) == "acrerca"  # odd length case

Test Summary

Test Why
"abba", 2 Provided example
"aa", 2 Rank exceeds total count
"bacab", 1 Odd-length palindrome
"a", 1 Smallest valid input
"a", 2 Single permutation only
"aaaa", 1 All characters identical
"aaaa", 2 Exceeding available permutations
"aabbaa" ranks 1-4 Verifies lexicographic ordering
"aaaabbbb" Multiple multinomial choices
"abcddcba" Larger character variety
Odd-length mixed case Verifies middle-character handling

Edge Cases

Rank Exceeds Total Number of Palindromes

A common bug is attempting to construct a result even when the requested rank does not exist. Before beginning the greedy process, the algorithm computes the total number of distinct half-string permutations. If this total is less than k, it immediately returns an empty string.

Only One Distinct Palindromic Rearrangement

Strings such as "aaaa" or "a" have exactly one valid palindromic arrangement. The greedy algorithm still works correctly because every position has only one available character. Any k > 1 is rejected during the initial count check.

Odd Length Palindromes

For strings like "bacab", one character appears an odd number of times. A frequent source of bugs is accidentally allowing that character to participate incorrectly in the half-string. The implementation stores the odd character separately as the center character and only uses count // 2 copies in the half counts. After constructing the left half, the middle character is inserted exactly once.

Extremely Large Numbers of Permutations

A half-string can have thousands of characters, causing multinomial coefficients to become astronomically large. Computing exact values would be expensive and unnecessary. Since the problem only requires comparison against k ≤ 10^6, the implementation caps all counts at 1,000,001. This preserves every comparison outcome while keeping arithmetic efficient and safe.

Large Input Length

The input length can reach 10^4. Any solution that generates permutations or repeatedly rebuilds large structures would be too slow. The implemented algorithm stores only frequency counts and constructs the answer directly, making it practical even at the maximum input size.

Problem Understanding

The problem asks us to find the k-th lexicographically smallest palindromic permutation of a given palindromic string s. In other words, we are given a string that reads the same forwards and backwards, and we must find the k-th distinct permutation of its characters that is also a palindrome, when all such permutations are sorted in lexicographic order.

The input s is guaranteed to be palindromic, which means that any valid permutation we generate must also be a palindrome. The integer k represents the 1-based index of the palindrome in lexicographic order. If there are fewer than k distinct palindromic permutations, we return an empty string.

Constraints indicate that s can be up to 10⁴ characters, and k can be up to 10⁶. This means brute-force enumeration of all permutations is impractical, and we need a combinatorial approach that counts possible palindromic permutations efficiently without generating them all.

Important edge cases include:

  • Strings with all identical characters, e.g., "aaaa". There is only one permutation.
  • Strings where k exceeds the total number of palindromic permutations.
  • Odd-length palindromes with a single middle character.

Approaches

Brute Force

The brute-force approach would generate all unique permutations of the string s and then filter only the palindromic ones. We would then sort the palindromes lexicographically and return the k-th. While this guarantees correctness, it is prohibitively slow. Generating all permutations has factorial time complexity $O(n!)$ and is infeasible for $n = 10^4$.

Optimal Approach

The key observation is that for a palindrome, the second half is a mirror of the first half. Therefore, the problem reduces to generating and counting permutations of the first half of s, along with the middle character if s has odd length. Using factorials and combinatorics, we can compute the number of palindromic permutations that begin with each candidate character without enumerating them. This allows us to construct the k-th palindrome greedily by selecting characters one at a time based on how many permutations remain.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Generate all permutations, filter palindromes, sort
Optimal O(n * 26) O(n + 26) Construct half-palindrome greedily using combinatorial counting

Algorithm Walkthrough

  1. Count characters: Use a frequency map to count occurrences of each character in s. Let count[c] denote the frequency of character c.

  2. Check for valid palindrome: Ensure that at most one character has an odd count. If more than one character has an odd count, no palindromic permutation is possible.

  3. Construct the first half: For each character c, let half[c] = count[c] // 2. This represents how many of c will appear in the first half of the palindrome.

  4. Precompute factorials: Compute factorials up to n // 2 to calculate multinomial coefficients efficiently.

  5. Greedy selection: To construct the first half lexicographically:

  6. For each position in the first half, iterate over characters in sorted order.

  7. Temporarily decrement half[c] and compute the number of palindromic permutations that can be formed with remaining counts.

  8. If k is greater than this count, subtract the count from k and restore half[c]. Otherwise, select c for this position, and proceed to the next position.

  9. Assemble palindrome: The final palindrome is the first half + middle character (if any) + reversed first half.

Why it works: The invariant is that at each step, k correctly represents the rank of the remaining permutations. By always selecting the smallest character whose count includes the k-th permutation, we guarantee lexicographic order.

Python Solution

from math import factorial
from collections import Counter

class Solution:
    def smallestPalindrome(self, s: str, k: int) -> str:
        count = Counter(s)
        n = len(s)
        mid = ''
        half = {}
        
        # Determine middle character for odd length
        for c in count:
            if count[c] % 2 == 1:
                if mid:
                    return ""  # More than one odd count, impossible
                mid = c
            half[c] = count[c] // 2
        
        # Precompute factorials up to n // 2
        max_half = sum(half.values())
        facts = [1] * (max_half + 1)
        for i in range(1, max_half + 1):
            facts[i] = facts[i-1] * i
        
        def count_perms(half_counts):
            total = sum(half_counts.values())
            res = facts[total]
            for c in half_counts:
                res //= facts[half_counts[c]]
            return res
        
        # Build first half
        first_half = []
        for _ in range(max_half):
            for c in sorted(half):
                if half[c] == 0:
                    continue
                half[c] -= 1
                cnt = count_perms(half)
                if k > cnt:
                    k -= cnt
                    half[c] += 1
                else:
                    first_half.append(c)
                    break
            else:
                return ""  # Should not reach here
        
        return "".join(first_half) + mid + "".join(reversed(first_half))

Explanation: We count characters, identify the middle character if present, and compute half-counts. Factorials are precomputed to calculate multinomial coefficients efficiently. The first half of the palindrome is constructed greedily by examining lexicographic candidates and using combinatorial counts to skip over blocks of permutations. Finally, we mirror the first half and append the middle character to form the full palindrome.

Go Solution

package main

import (
    "sort"
    "strings"
)

func smallestPalindrome(s string, k int) string {
    count := make(map[rune]int)
    for _, c := range s {
        count[c]++
    }
    
    var mid rune
    half := make(map[rune]int)
    for c, v := range count {
        if v%2 == 1 {
            if mid != 0 {
                return ""
            }
            mid = c
        }
        half[c] = v / 2
    }
    
    maxHalf := 0
    for _, v := range half {
        maxHalf += v
    }
    
    facts := make([]int, maxHalf+1)
    facts[0] = 1
    for i := 1; i <= maxHalf; i++ {
        facts[i] = facts[i-1] * i
    }
    
    var keys []rune
    for c := range half {
        keys = append(keys, c)
    }
    sort.Slice(keys, func(i, j int) bool { return keys[i] < keys[j] })
    
    countPerms := func(halfCounts map[rune]int) int {
        total := 0
        for _, v := range halfCounts {
            total += v
        }
        res := facts[total]
        for _, v := range halfCounts {
            res /= facts[v]
        }
        return res
    }
    
    var firstHalf []rune
    for i := 0; i < maxHalf; i++ {
        found := false
        for _, c := range keys {
            if half[c] == 0 {
                continue
            }
            half[c]--
            cnt := countPerms(half)
            if k > cnt {
                k -= cnt
                half[c]++
            } else {
                firstHalf = append(firstHalf, c)
                found = true
                break
            }
        }
        if !found {
            return ""
        }
    }
    
    var sb strings.Builder
    for _, c := range firstHalf {
        sb.WriteRune(c)
    }
    if mid != 0 {
        sb.WriteRune(mid)
    }
    for i := len(firstHalf) - 1; i >= 0; i-- {
        sb.WriteRune(firstHalf[i])
    }
    
    return sb.String()
}

Explanation: The Go solution mirrors the Python logic. Rune maps are used for character counting. Factorials are precomputed in an integer slice. Lexicographic selection of characters uses sorting of keys. Strings.Builder efficiently concatenates characters to form the final palindrome.

Worked Examples

Example 1: s = "abba", k = 2

  1. Count: {'a':2,'b':2}, mid = '', half = {'a':1,'b':1}
  2. maxHalf = 2, factorials: [1,1,2]
  3. First position: try 'a' → 1 remaining permutation ('ba') → k=2>1 → skip, k=1, restore 'a'
  4. First position: try 'b' → 1 remaining permutation → select 'b', first_half = ['b']
  5. Second position: only 'a' left → select 'a', first_half = ['b','a']
  6. Result = "baab"

Example 2: s = "aa", k = 2