• Leetcode 3518. Smallest Palindromic Rearrangement II
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：Leetcode 3518. Smallest Palindromic Rearrangement II

1. 解題思路

這一題是題目Leetcode 3517. Smallest Palindromic Rearrangement I的升級版本，其主要的升級點就是要求按字典序排序第$k$小的字符串，而不是簡單的直接獲取最小的字符串了。因此處理起來事實上要多做的部分也就是如何求這個第$k$小的字符串。

我們首先看一下前置的內容，即首先我們需要找到這個回文的唯一部分，即其前半段所包含的全部字符，這個我們只需要將原始字符串進行一下字符統計，然后取所有字符的一半即可。此時，我們將其任意排列，然后拼湊其反向字符即可得到一個滿足條件的回文。

因此，要求其第$k$小的回文字符串，事實上也就是求這個前半段字符的第$k$小的字符串排列。

顯然，經過簡單的數學知識，我們已知一個長度為$n$的字符串序列，其可能的字符排列的種類一共有：

$$N=\frac{n!}{\underset{i=1}{\overset{m}{\Pi }}{n}_i!}$$

因此，我們只需要一個遞推算法，逐一考察從頭開始每一個元素依次從小到大擺放各個字符時其剩余的字符串排列的數目是否大于剩余需要的字符串排列數目即可。

用偽代碼表示即為：

def get_kth_string(s, k):cnt = Counter(s)ans = ""while k > 1:for ch in [a..z]:cnt[ch] -= 1m = factorial(n)for _ch in [a..z]:m = m // factorial[_ch]if m >= k:ans += chelse:k -= mcnt[ch] += 1ans += "".join(ch * cnt[ch] for ch in [a..z])return ans

整體的算法復雜度就是$O(N\times 26^2)$

2. 代碼實現

給出最終的python代碼實現如下：

class Solution:def get_kth_smallest_string(self, s, k):cnt = Counter(s)n = len(s)def c(n, m, upper):m = min(n-m, m)ans = 1for i in range(m):ans = ans * (n-i) // (i+1)if ans >= upper:return ansreturn ansdef get_count(cnt, upper):n = sum(cnt.values())ans = 1for m in cnt.values():ans = ans * c(n, m, upper)n -= mif ans >= upper:return ansreturn anstot = get_count(cnt, k)if k == 1:return "".join(sorted(s))elif tot < k:return ""def dfs(idx, k):if k == 1:return "".join([ch * cnt[ch] for ch in string.ascii_lowercase])for ch in string.ascii_lowercase:if cnt[ch] > 0:cnt[ch] -= 1tot = get_count(cnt, k)if tot >= k:return ch + dfs(idx+1, k)k -= totcnt[ch] += 1return ""return dfs(0, k)def smallestPalindrome(self, s: str, k: int) -> str:cnt = Counter(s)mid = ""ans = ""for ch in string.ascii_lowercase:ans += ch * (cnt[ch] // 2)if cnt[ch] % 2 == 1:mid = chif ans == "":return mid if k == 1 else ""ans = self.get_kth_smallest_string(ans, k)return ans + mid + ans[::-1] if ans != "" else ""

提交代碼評測得到：耗時1055ms，占用內存19.4MB。