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

这道题要求在给定的 回文串 s 的所有不同的回文排列中，按 字典序 找出第 k 小的回文排列。如果不同的回文排列总数不足 k 个，则返回空字符串 ""。

解题思路

转化问题：
- 因为字符串是回文串，所以整个回文串完全由其 左半部分（长度为 n // 2）确定。
- 如果字符串长度为奇数，中间的字符是固定的（即 s[n // 2]）。
- 因此，整个回文串按字典序排列，等价于其左半部分按字典序排列。
- 题目转化为：计算由 s 的左半部分字符构成的多重集排列，求其按字典序第 k 小的左半部分。
多重集排列数计算（组合数学）：
- 假设当前剩余的待排列字符频次为 cnt，总字符数为 total = sum(cnt)。
- 这些字符能构成的不同排列数为： $ways = \prod_{i = 0}^{25} (\binom{{total}_{i}}{cnt [i]})$ 其中 ${total}_{i}$ 是除去前 $i - 1$ 种字符后剩余的位置数。
- 由于 $k \leq 10^{6}$ ，当组合数乘积达到 $k + 1$ 时即可 截断 (Limit)，避免产生巨大的大数运算，保证计算效率。
逐位确定（逐字符试填法）：
- 从左到右依次确定左半部分的每个位置。
- 对于每个位置，按照字母表顺序 'a' 到 'z' 尝试填入字符 c：
  - 若字符 c 的剩余频次大于 0，假设将 c 填入当前位置，计算剩余字符能够构成的不同排列数 ways。
  - 如果 $k \leq ways$ ，说明目标排列就在以 c 开头的分支中，因此确定当前位置填入 c，跳出内层循环。
  - 如果 $k > ways$ ，说明以 c 开头的分支不够 $k$ 个，将 $k$ 减去 ways（ $k \leftarrow k - ways$ ），撤销选择并尝试下一个字符。
拼接完整回文串：
- 构造出左半部分 left 后，最终答案即为 left + mid + left[::-1]。

Python3 代码实现

python

import math


class Solution:

  def smallestPalindrome(self, s: str, k: int) -> str:
    n = len(s)
    half_len = n // 2
    # 奇数长度时确定中间字符，偶数长度时为空字符串
    mid = s[half_len] if n % 2 == 1 else ""

    # 统计左半部分的字符频次
    cnt = [0] * 26
    for i in range(half_len):
      cnt[ord(s[i]) - ord("a")] += 1

    # 上限截断值，避免无意义的大数乘法
    LIMIT = k + 1

    # 计算多重集排列数，超过 LIMIT 时立即截断
    def count_arrangements(counts: list[int]) -> int:
      total = sum(counts)
      res = 1
      for c in counts:
        if c == 0:
          continue
        res *= math.comb(total, c)
        total -= c
        if res >= LIMIT:
          return LIMIT
      return res

    # 如果总排列数小于 k，说明不存在第 k 个回文排列
    if count_arrangements(cnt) < k:
      return ""

    left = []
    # 逐位试填左半部分的字符
    for _ in range(half_len):
      for i in range(26):
        if cnt[i] == 0:
          continue

        # 尝试将字符 i 填入当前位
        cnt[i] -= 1
        ways = count_arrangements(cnt)

        if k <= ways:
          # 目标在当前分支，确定填入字符 i
          left.append(chr(ord("a") + i))
          break
        else:
          # 不在当前分支，恢复频次并跳过
          cnt[i] += 1
          k -= ways

    left_str = "".join(left)
    # 拼接最终的回文串
    return left_str + mid + left_str[::-1]

复杂度分析

时间复杂度： $O (n + \frac{n}{2} \times 26) = O (n)$ 。
- 统计频次需要 $O (n)$ 时间。
- 左半部分有 $m = n / 2$ 个位置，每个位置最多枚举 26 个字符。
- count_arrangements 函数内部在乘积超过 k + 1 后会触发提前返回（通常仅需循环 1~3 次），因此每次调用可视为 $O (1)$ 时间。
- Overall 运行时间非常高效，可以远低于 0.1 秒通过 $n = 10^{4}$ 的数据。
空间复杂度： $O (n)$ 。
- 辅助频次数组大小固定为 26，存储答案的数组大小为 $O (n)$ 。

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