LeetCode #3518 — HARD

Smallest Palindromic Rearrangement II

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

You are given a palindromic string s and an integer k.

Return the k-th lexicographically smallest palindromic permutation of s. If there are fewer than k distinct palindromic permutations, return an empty string.

Note: Different rearrangements that yield the same palindromic string are considered identical and are counted once.

Example 1:

Input: s = "abba", k = 2

Output: "baab"

Explanation:

The two distinct palindromic rearrangements of "abba" are "abba" and "baab".
Lexicographically, "abba" comes before "baab". Since k = 2, the output is "baab".

Example 2:

Input: s = "aa", k = 2

Output: ""

Explanation:

There is only one palindromic rearrangement: "aa".
The output is an empty string since k = 2 exceeds the number of possible rearrangements.

Example 3:

Input: s = "bacab", k = 1

Output: "abcba"

Explanation:

The two distinct palindromic rearrangements of "bacab" are "abcba" and "bacab".
Lexicographically, "abcba" comes before "bacab". Since k = 1, the output is "abcba".

Constraints:

1 <= s.length <= 10⁴
s consists of lowercase English letters.
s is guaranteed to be palindromic.
1 <= k <= 10⁶

Step 01

Brute Force Baseline

Problem summary: You are given a palindromic string s and an integer k. Return the k-th lexicographically smallest palindromic permutation of s. If there are fewer than k distinct palindromic permutations, return an empty string. Note: Different rearrangements that yield the same palindromic string are considered identical and are counted once.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Hash Map · Math

Example 1

"abba"
2

Example 2

"aa"
2

Example 3

"bacab"
1

Step 02

Core Insight

What unlocks the optimal approach

Only build <code>floor(n / 2)</code> characters (the rest are determined by symmetry).
Count character frequencies and use half the counts for construction.
Incrementally choose each character (from smallest to largest) and calculate how many valid arrangements result if that character is chosen at the current index.
If the count is at least <code>k</code>, fix that character; otherwise, subtract the count from <code>k</code> and try the next candidate.
Use combinatorics to compute the number of permutations at each step.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3518: Smallest Palindromic Rearrangement II
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3518: Smallest Palindromic Rearrangement II
// package main
// 
// import (
// 	"bytes"
// 	"slices"
// )
// 
// // https://space.bilibili.com/206214
// func smallestPalindrome(s string, k int) string {
// 	n := len(s)
// 	m := n / 2
// 
// 	total := [26]int{}
// 	for _, b := range s[:m] {
// 		total[b-'a']++
// 	}
// 
// 	cnt := make([]int, 26)
// 	perm := 1
// 	i, j := m-1, 25
// 	// 倒着计算排列数
// 	for ; i >= 0 && perm < k; i-- {
// 		for cnt[j] == total[j] {
// 			j--
// 		}
// 		cnt[j]++
// 		perm = perm * (m - i) / cnt[j]
// 	}
// 
// 	if perm < k {
// 		return ""
// 	}
// 
// 	ans := make([]byte, 0, n)
// 	// 已经有足够的排列数了，<= i 的位置直接填字典序最小的排列
// 	for ch, c := range cnt[:j+1] {
// 		ans = append(ans, bytes.Repeat([]byte{'a' + byte(ch)}, total[ch]-c)...)
// 	}
// 
// 	// 试填法
// 	j0 := j
// 	for i++; i < m; i++ {
// 		for j := j0; j < 26; j++ {
// 			if cnt[j] == 0 {
// 				continue
// 			}
// 			// 假设填字母 j，根据 perm = p * (m - i) / cnt[j] 倒推 p
// 			p := perm * cnt[j] / (m - i)
// 			if p >= k {
// 				ans = append(ans, 'a'+byte(j))
// 				cnt[j]--
// 				perm = p
// 				break
// 			}
// 			k -= p
// 		}
// 	}
// 
// 	rev := slices.Clone(ans)
// 	if n%2 > 0 {
// 		ans = append(ans, s[n/2])
// 	}
// 	slices.Reverse(rev)
// 	ans = append(ans, rev...)
// 	return string(ans)
// }
// 
// func smallestPalindrome1(s string, k int) string {
// 	n := len(s)
// 	m := n / 2
// 	cnt := make([]int, 26)
// 	for _, b := range s[:m] {
// 		cnt[b-'a']++
// 	}
// 
// 	// 为什么这样做是对的？见 62. 不同路径 我的题解
// 	comb := func(n, m int) int {
// 		m = min(m, n-m)
// 		res := 1
// 		for i := 1; i <= m; i++ {
// 			res = res * (n + 1 - i) / i
// 			if res >= k { // 太大了
// 				return k
// 			}
// 		}
// 		return res
// 	}
// 
// 	// 计算长为 sz 的字符串的排列个数
// 	perm := func(sz int) int {
// 		res := 1
// 		for _, c := range cnt {
// 			if c == 0 {
// 				continue
// 			}
// 			// 先从 sz 个里面选 c 个位置填当前字母
// 			res *= comb(sz, c)
// 			if res >= k { // 太大了
// 				return k
// 			}
// 			// 从剩余位置中选位置填下一个字母
// 			sz -= c
// 		}
// 		return res
// 	}
// 
// 	// k 太大
// 	if perm(m) < k {
// 		return ""
// 	}
// 
// 	// 构造回文串的左半部分
// 	ans := make([]byte, m, n)
// 	for i := range m {
// 		for j := range cnt {
// 			if cnt[j] == 0 {
// 				continue
// 			}
// 			cnt[j]--             // 假设填字母 j，看是否有足够的排列
// 			p := perm(m - i - 1) // 剩余位置的排列个数
// 			if p >= k {          // 有足够的排列
// 				ans[i] = 'a' + byte(j)
// 				break
// 			}
// 			k -= p // k 太大，要填更大的字母（类似搜索树剪掉了一个大小为 p 的子树）
// 			cnt[j]++
// 		}
// 	}
// 
// 	rev := slices.Clone(ans)
// 	if n%2 > 0 {
// 		ans = append(ans, s[n/2])
// 	}
// 	slices.Reverse(rev)
// 	ans = append(ans, rev...)
// 	return string(ans)
// }

// Accepted solution for LeetCode #3518: Smallest Palindromic Rearrangement II
package main

import (
	"bytes"
	"slices"
)

// https://space.bilibili.com/206214
func smallestPalindrome(s string, k int) string {
	n := len(s)
	m := n / 2

	total := [26]int{}
	for _, b := range s[:m] {
		total[b-'a']++
	}

	cnt := make([]int, 26)
	perm := 1
	i, j := m-1, 25
	// 倒着计算排列数
	for ; i >= 0 && perm < k; i-- {
		for cnt[j] == total[j] {
			j--
		}
		cnt[j]++
		perm = perm * (m - i) / cnt[j]
	}

	if perm < k {
		return ""
	}

	ans := make([]byte, 0, n)
	// 已经有足够的排列数了，<= i 的位置直接填字典序最小的排列
	for ch, c := range cnt[:j+1] {
		ans = append(ans, bytes.Repeat([]byte{'a' + byte(ch)}, total[ch]-c)...)
	}

	// 试填法
	j0 := j
	for i++; i < m; i++ {
		for j := j0; j < 26; j++ {
			if cnt[j] == 0 {
				continue
			}
			// 假设填字母 j，根据 perm = p * (m - i) / cnt[j] 倒推 p
			p := perm * cnt[j] / (m - i)
			if p >= k {
				ans = append(ans, 'a'+byte(j))
				cnt[j]--
				perm = p
				break
			}
			k -= p
		}
	}

	rev := slices.Clone(ans)
	if n%2 > 0 {
		ans = append(ans, s[n/2])
	}
	slices.Reverse(rev)
	ans = append(ans, rev...)
	return string(ans)
}

func smallestPalindrome1(s string, k int) string {
	n := len(s)
	m := n / 2
	cnt := make([]int, 26)
	for _, b := range s[:m] {
		cnt[b-'a']++
	}

	// 为什么这样做是对的？见 62. 不同路径 我的题解
	comb := func(n, m int) int {
		m = min(m, n-m)
		res := 1
		for i := 1; i <= m; i++ {
			res = res * (n + 1 - i) / i
			if res >= k { // 太大了
				return k
			}
		}
		return res
	}

	// 计算长为 sz 的字符串的排列个数
	perm := func(sz int) int {
		res := 1
		for _, c := range cnt {
			if c == 0 {
				continue
			}
			// 先从 sz 个里面选 c 个位置填当前字母
			res *= comb(sz, c)
			if res >= k { // 太大了
				return k
			}
			// 从剩余位置中选位置填下一个字母
			sz -= c
		}
		return res
	}

	// k 太大
	if perm(m) < k {
		return ""
	}

	// 构造回文串的左半部分
	ans := make([]byte, m, n)
	for i := range m {
		for j := range cnt {
			if cnt[j] == 0 {
				continue
			}
			cnt[j]--             // 假设填字母 j，看是否有足够的排列
			p := perm(m - i - 1) // 剩余位置的排列个数
			if p >= k {          // 有足够的排列
				ans[i] = 'a' + byte(j)
				break
			}
			k -= p // k 太大，要填更大的字母（类似搜索树剪掉了一个大小为 p 的子树）
			cnt[j]++
		}
	}

	rev := slices.Clone(ans)
	if n%2 > 0 {
		ans = append(ans, s[n/2])
	}
	slices.Reverse(rev)
	ans = append(ans, rev...)
	return string(ans)
}

# Accepted solution for LeetCode #3518: Smallest Palindromic Rearrangement II
class Solution:
  def __init__(self):
    self.MAX = 10**6 + 1

  def smallestPalindrome(self, s: str, k: int) -> str:
    count = collections.Counter(s)
    if not self._isPalindromePossible(count):
      return ''

    halfCount, midLetter = self._getHalfCountAndMidLetter(count)
    totalPerm = self._calculateTotalPermutations(halfCount)
    if k > totalPerm:
      return ''
    leftHalf = self._generateLeftHalf(halfCount, k)
    return ''.join(leftHalf) + midLetter + ''.join(reversed(leftHalf))

  def _isPalindromePossible(self, count: collections.Counter) -> bool:
    oddCount = sum(1 for count in count.values() if count % 2 == 1)
    return oddCount <= 1

  def _getHalfCountAndMidLetter(self, count: collections.Counter) -> tuple[list[int], str]:
    halfCount = [0] * 26
    midLetter = ''
    for c, freq in count.items():
      halfCount[ord(c) - ord('a')] = freq // 2
      if freq % 2 == 1:
        midLetter = c
    return halfCount, midLetter

  def _calculateTotalPermutations(self, halfCount: list[int]) -> int:
    """Calculate the total number of possible permutations."""
    return self._countArrangements(halfCount)

  def _generateLeftHalf(self, halfCount: list[int], k: int) -> list[str]:
    """Generate the left half of the palindrome based on k."""
    halfLen = sum(halfCount)
    left = []
    for _ in range(halfLen):
      for i, freq in enumerate(halfCount):
        if freq == 0:
          continue
        halfCount[i] -= 1
        arrangements = self._countArrangements(halfCount)
        if arrangements >= k:
          left.append(chr(i + ord('a')))
          break
        else:
          k -= arrangements
          halfCount[i] += 1
    return left

  def _countArrangements(self, count: list[int]) -> int:
    """Calculate the number of possible arrangements of characters."""
    total = sum(count)
    res = 1
    for freq in count:
      res *= self._nCk(total, freq)
      if res >= self.MAX:
        return self.MAX
      total -= freq
    return res

  def _nCk(self, n: int, k: int) -> int:
    res = 1
    for i in range(1, min(k, n - k) + 1):
      res = res * (n - i + 1) // i
      if res >= self.MAX:
        return self.MAX
    return res

// Accepted solution for LeetCode #3518: Smallest Palindromic Rearrangement II
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (go):
// // Accepted solution for LeetCode #3518: Smallest Palindromic Rearrangement II
// package main
// 
// import (
// 	"bytes"
// 	"slices"
// )
// 
// // https://space.bilibili.com/206214
// func smallestPalindrome(s string, k int) string {
// 	n := len(s)
// 	m := n / 2
// 
// 	total := [26]int{}
// 	for _, b := range s[:m] {
// 		total[b-'a']++
// 	}
// 
// 	cnt := make([]int, 26)
// 	perm := 1
// 	i, j := m-1, 25
// 	// 倒着计算排列数
// 	for ; i >= 0 && perm < k; i-- {
// 		for cnt[j] == total[j] {
// 			j--
// 		}
// 		cnt[j]++
// 		perm = perm * (m - i) / cnt[j]
// 	}
// 
// 	if perm < k {
// 		return ""
// 	}
// 
// 	ans := make([]byte, 0, n)
// 	// 已经有足够的排列数了，<= i 的位置直接填字典序最小的排列
// 	for ch, c := range cnt[:j+1] {
// 		ans = append(ans, bytes.Repeat([]byte{'a' + byte(ch)}, total[ch]-c)...)
// 	}
// 
// 	// 试填法
// 	j0 := j
// 	for i++; i < m; i++ {
// 		for j := j0; j < 26; j++ {
// 			if cnt[j] == 0 {
// 				continue
// 			}
// 			// 假设填字母 j，根据 perm = p * (m - i) / cnt[j] 倒推 p
// 			p := perm * cnt[j] / (m - i)
// 			if p >= k {
// 				ans = append(ans, 'a'+byte(j))
// 				cnt[j]--
// 				perm = p
// 				break
// 			}
// 			k -= p
// 		}
// 	}
// 
// 	rev := slices.Clone(ans)
// 	if n%2 > 0 {
// 		ans = append(ans, s[n/2])
// 	}
// 	slices.Reverse(rev)
// 	ans = append(ans, rev...)
// 	return string(ans)
// }
// 
// func smallestPalindrome1(s string, k int) string {
// 	n := len(s)
// 	m := n / 2
// 	cnt := make([]int, 26)
// 	for _, b := range s[:m] {
// 		cnt[b-'a']++
// 	}
// 
// 	// 为什么这样做是对的？见 62. 不同路径 我的题解
// 	comb := func(n, m int) int {
// 		m = min(m, n-m)
// 		res := 1
// 		for i := 1; i <= m; i++ {
// 			res = res * (n + 1 - i) / i
// 			if res >= k { // 太大了
// 				return k
// 			}
// 		}
// 		return res
// 	}
// 
// 	// 计算长为 sz 的字符串的排列个数
// 	perm := func(sz int) int {
// 		res := 1
// 		for _, c := range cnt {
// 			if c == 0 {
// 				continue
// 			}
// 			// 先从 sz 个里面选 c 个位置填当前字母
// 			res *= comb(sz, c)
// 			if res >= k { // 太大了
// 				return k
// 			}
// 			// 从剩余位置中选位置填下一个字母
// 			sz -= c
// 		}
// 		return res
// 	}
// 
// 	// k 太大
// 	if perm(m) < k {
// 		return ""
// 	}
// 
// 	// 构造回文串的左半部分
// 	ans := make([]byte, m, n)
// 	for i := range m {
// 		for j := range cnt {
// 			if cnt[j] == 0 {
// 				continue
// 			}
// 			cnt[j]--             // 假设填字母 j，看是否有足够的排列
// 			p := perm(m - i - 1) // 剩余位置的排列个数
// 			if p >= k {          // 有足够的排列
// 				ans[i] = 'a' + byte(j)
// 				break
// 			}
// 			k -= p // k 太大，要填更大的字母（类似搜索树剪掉了一个大小为 p 的子树）
// 			cnt[j]++
// 		}
// 	}
// 
// 	rev := slices.Clone(ans)
// 	if n%2 > 0 {
// 		ans = append(ans, s[n/2])
// 	}
// 	slices.Reverse(rev)
// 	ans = append(ans, rev...)
// 	return string(ans)
// }

// Accepted solution for LeetCode #3518: Smallest Palindromic Rearrangement II
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3518: Smallest Palindromic Rearrangement II
// package main
// 
// import (
// 	"bytes"
// 	"slices"
// )
// 
// // https://space.bilibili.com/206214
// func smallestPalindrome(s string, k int) string {
// 	n := len(s)
// 	m := n / 2
// 
// 	total := [26]int{}
// 	for _, b := range s[:m] {
// 		total[b-'a']++
// 	}
// 
// 	cnt := make([]int, 26)
// 	perm := 1
// 	i, j := m-1, 25
// 	// 倒着计算排列数
// 	for ; i >= 0 && perm < k; i-- {
// 		for cnt[j] == total[j] {
// 			j--
// 		}
// 		cnt[j]++
// 		perm = perm * (m - i) / cnt[j]
// 	}
// 
// 	if perm < k {
// 		return ""
// 	}
// 
// 	ans := make([]byte, 0, n)
// 	// 已经有足够的排列数了，<= i 的位置直接填字典序最小的排列
// 	for ch, c := range cnt[:j+1] {
// 		ans = append(ans, bytes.Repeat([]byte{'a' + byte(ch)}, total[ch]-c)...)
// 	}
// 
// 	// 试填法
// 	j0 := j
// 	for i++; i < m; i++ {
// 		for j := j0; j < 26; j++ {
// 			if cnt[j] == 0 {
// 				continue
// 			}
// 			// 假设填字母 j，根据 perm = p * (m - i) / cnt[j] 倒推 p
// 			p := perm * cnt[j] / (m - i)
// 			if p >= k {
// 				ans = append(ans, 'a'+byte(j))
// 				cnt[j]--
// 				perm = p
// 				break
// 			}
// 			k -= p
// 		}
// 	}
// 
// 	rev := slices.Clone(ans)
// 	if n%2 > 0 {
// 		ans = append(ans, s[n/2])
// 	}
// 	slices.Reverse(rev)
// 	ans = append(ans, rev...)
// 	return string(ans)
// }
// 
// func smallestPalindrome1(s string, k int) string {
// 	n := len(s)
// 	m := n / 2
// 	cnt := make([]int, 26)
// 	for _, b := range s[:m] {
// 		cnt[b-'a']++
// 	}
// 
// 	// 为什么这样做是对的？见 62. 不同路径 我的题解
// 	comb := func(n, m int) int {
// 		m = min(m, n-m)
// 		res := 1
// 		for i := 1; i <= m; i++ {
// 			res = res * (n + 1 - i) / i
// 			if res >= k { // 太大了
// 				return k
// 			}
// 		}
// 		return res
// 	}
// 
// 	// 计算长为 sz 的字符串的排列个数
// 	perm := func(sz int) int {
// 		res := 1
// 		for _, c := range cnt {
// 			if c == 0 {
// 				continue
// 			}
// 			// 先从 sz 个里面选 c 个位置填当前字母
// 			res *= comb(sz, c)
// 			if res >= k { // 太大了
// 				return k
// 			}
// 			// 从剩余位置中选位置填下一个字母
// 			sz -= c
// 		}
// 		return res
// 	}
// 
// 	// k 太大
// 	if perm(m) < k {
// 		return ""
// 	}
// 
// 	// 构造回文串的左半部分
// 	ans := make([]byte, m, n)
// 	for i := range m {
// 		for j := range cnt {
// 			if cnt[j] == 0 {
// 				continue
// 			}
// 			cnt[j]--             // 假设填字母 j，看是否有足够的排列
// 			p := perm(m - i - 1) // 剩余位置的排列个数
// 			if p >= k {          // 有足够的排列
// 				ans[i] = 'a' + byte(j)
// 				break
// 			}
// 			k -= p // k 太大，要填更大的字母（类似搜索树剪掉了一个大小为 p 的子树）
// 			cnt[j]++
// 		}
// 	}
// 
// 	rev := slices.Clone(ans)
// 	if n%2 > 0 {
// 		ans = append(ans, s[n/2])
// 	}
// 	slices.Reverse(rev)
// 	ans = append(ans, rev...)
// 	return string(ans)
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(n)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.

HASH MAP

O(n) time

O(n) space

One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.

Shortcut: Need to check “have I seen X before?” → hash map → O(n) time, O(n) space.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.