3518. Smallest Palindromic Rearrangement II LeetCode Solution

Last updated: April 22, 2025

In this guide, you will get 3518. Smallest Palindromic Rearrangement II LeetCode Solution with the best time and space complexity. The solution to Smallest Palindromic Rearrangement II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Smallest Palindromic Rearrangement II solution in C++
Smallest Palindromic Rearrangement II solution in Java
Smallest Palindromic Rearrangement II solution in Python
Additional Resources

3518. Smallest Palindromic Rearrangement II LeetCode Solution image

Problem Statement of Smallest Palindromic Rearrangement II

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 <= 104
s consists of lowercase English letters.
s is guaranteed to be palindromic.
1 <= k <= 106

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

3518. Smallest Palindromic Rearrangement II LeetCode Solution in C++

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
/* code provided by PROGIEZ */

3518. Smallest Palindromic Rearrangement II LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3518. Smallest Palindromic Rearrangement II LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents