3518.最小回文排列II

hash table, math, string, combinatorics, counting, https://leetcode.cn/problems/smallest-palindromic-rearrangement-ii/

给你一个回文字符串 s 和一个整数 k。

返回 s 的按字典序排列的 第 k 小 回文排列。如果不存在 k 个不同的回文排列，则返回空字符串。

注意： 产生相同回文字符串的不同重排视为相同，仅计为一次。

如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个回文字符串。

排列是字符串中所有字符的重排。

如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。

示例 1：

输入： s = "abba", k = 2

输出： "baab"

解释：

"abba" 的两个不同的回文排列是 "abba" 和 "baab"。
按字典序，"abba" 位于 "baab" 之前。由于 k = 2，输出为 "baab"。

示例 2：

输入： s = "aa", k = 2

输出： ""

解释：

仅有一个回文排列："aa"。
由于 k = 2 超过了可能的排列数，输出为空字符串。

示例 3：

输入： s = "bacab", k = 1

输出： "abcba"

解释：

"bacab" 的两个不同的回文排列是 "abcba" 和 "bacab"。
按字典序，"abcba" 位于 "bacab" 之前。由于 k = 1，输出为 "abcba"。

提示：

1 <= s.length <= 10^4
s 由小写英文字母组成。
保证 s 是回文字符串。
1 <= k <= 10^6

python

from collections import Counter


class Solution:
    def smallestPalindrome(self, s: str, k: int) -> str:
        cnt = Counter(s)
        # 1. 构造半串计数和中间字符
        half = {}
        mid = ''
        m = 0
        for ch in sorted(cnt):
            c = cnt[ch]
            if c & 1:
                mid = ch
            half[ch] = c // 2
            m += c // 2

        # 2. 预计算 factorial[0..m]
        fact = [1] * (m + 1)
        for i in range(1, m + 1):
            fact[i] = fact[i - 1] * i

        # 初始的总排列数 = m! / ∏(half[ch]!)
        total = fact[m]
        for v in half.values():
            total //= fact[v]
        if total < k:
            return ""  # 不足 k 个

        # 3. 增量生成第 k 小半串
        left = []
        rem = m
        # 当前“可用排列数”为 total = rem! / ∏(half[ch]!)
        for _ in range(m):
            # 在每个位置，按字典序尝试
            for ch in half:
                v = half[ch]
                if v == 0:
                    continue
                # 如果我们把一个 ch 放到当前位置，
                # 剩余的排列数 new_total = total * v / rem
                # （因为 rem!/(v!·…) → (rem-1)!/((v-1)!·…) = total * v / rem）
                cnt_here = total * v // rem
                if cnt_here >= k:
                    # 选中 ch
                    left.append(ch)
                    # 更新 total、half、rem
                    total = cnt_here
                    half[ch] -= 1
                    rem -= 1
                    break
                # 否则跳过 ch
                k -= cnt_here

        # 拼回文
        half_str = ''.join(left)
        return half_str + mid + half_str[::-1]


if __name__ == "__main__":
    sol = Solution()
    print(sol.smallestPalindrome("abba", 1))  # "baab"
    print(sol.smallestPalindrome("aa", 2))  # ""

3518.最小回文排列II ​

3518.最小回文排列II