组合数学

题目分析 本题要求的是将$s$重排形成的所有回文串进行排序，并返回第$k$小的那个回文串。 基本思路 首先，既然题目要求将本就是回文串的$s$重排形成另外的回文串，那么实际上需要重排的只是$s$的左边一半，只要得到左边一半的所有字符组成的所有排列中第$k$小的排列，那么将它倒序后和它进行拼接即可得到答案（注意，如果原字符串长度为奇数，则需要将$s$的中间字符插在两个拼接的排列中间，因为整个字符串中只有这一个字符出现了奇数次，无论如何它都必须放在中间）。 因此，问题就转换成了：取出$s$的左边一半$left$，并求它形成的第$k$小的排列。 但，怎么找出第$k$小的排列呢？注意到，如果将一个字符串重排形成的所有排列放在一个列表中进行从小到大排序，那么排完之后，列表中所有元素的首字母一定从左到右是非递减的，同样的，在首字母相同的一段排列中，第2个字母一定从左到右也是非递减的，以此类推，只要一段排列的前$x$个字符都相同，那么它们的第$x+1$个字符一定从左到右是非递减的。综上所述，如果要找到第$k$小的那个排列，可以考虑在每一个位置按照字母从小到大的顺序依次尝试填入，即可保证得到的排列一定是不断变大的。 不过如果直接这样暴力模拟填写字母直到第$k$个，最坏情况下可能要将所有可能的排列都遍历完，复杂度可能达到$O(26^n)$，一定超时。那么如果能够在每一个位置都可以只循环一遍剩余能填的字母就判断出这个位置该填哪个，时间复杂度最坏情况下也只有$O(26n)$（每个位置都遍历所有字母），就可以通过。 如何实现？对于第一个位置，首先从小到大遍历可以选的所有字母，假如现在在第一个位置填上某一个字母，那么后面能填的各种字母的个数必定发生变化，根据剩余字母的个数，结合组合数学即可求出后面$n-1$个位置所有排列的总情况数，加上之前累计的情况数即可得到在该情况下能够达到最大的排列是第几小，如果还未超过$k$，就直接加到累计情况总数中，继续尝试下一个字母，否则，只要大于等于$k$，就不累加并进入到下一个位置的选择中。 这样，从头开始逐位挑选合适的字符，即可让累计情况数不断向$k$逼近，最终到达$k$，将填出来的字串还原即得答案。当然，如果最终选不出和$left$一样长的字符串，就说明总情况数小于$k$，返回"“即可。 计算组合数方法即代码优化 根据上面所说，程序中需要根据一个字符串中各个字符的个数计算它们能够组成的不同排列总数。假设剩余字符总个数为$m$，且$cnt[x]$表示字符$x$的剩余个数，那么不同的排列总数就是： $$ \frac{m!}{cnt[a]!\times cnt[b]!\times \cdots \times cnt[z]!} $$ 上面是未考虑重复字符情况下的总排列数，下面是针对每个字符的重复次数进行去重。 但如果每次计算时都遍历一次所有字母计算排列总数，大数计算次数太多，太慢了，需要进行优化。注意到，如果位置$i$选择填字母$x$，令$m$为从$i$开始到左半边字符串结尾的长度，那么在修改$cnt$数组数据之前计算出来的排列总数为： $$ \frac{m!}{cnt[a]!\times \cdots \times cnt[x]!\times \cdots \times cnt[z]!} $$ 而在修改后计算出来的排列总数为： $$ \frac{(m-1)!}{cnt[a]!\times \cdots \times (cnt[x]-1)!\times \cdots \times cnt[z]!} $$注意到，后者比前者的分母少了$m$，分子少了$cnt[x]$，因此，如果能够保存下来上一个位置选定字母后剩余位置的排列总数$last$，当前选定字母后剩余位置的排列总数就是： $$ last\times \frac{cnt[x]}{m} $$综上所述，如果最开始能够计算出来总共的排列总数，即可在循环中用滚动计算得到当前情况下剩余位置的排列总数。 复杂度 时间复杂度：$O(nlogn)$ 空间复杂度：$O(n)$ 代码 maxNum = 10001 prod = [1]*maxNum for i in range(1, maxNum): prod[i] = prod[i-1]*i def comb(m, n): return prod[m]//(prod[m-n]*prod[n]) class Solution: def smallestPalindrome(self, s: str, k: int) -> str: n = len(s) left = s[:n//2] cnt = [0]*26 for c in left: cnt[ord(c)-ord('a')] += 1 val = prod[n//2] # 计算所有位置的排列总数 for i in cnt: if i == 0: continue val //= prod[i] left = ''.join(sorted(left)) res = "" counted = 0 # 累计排列总数 for i in range(n//2): for j in range(26): # 从小到大试填 if cnt[j]: # 第j个字符还有剩余 cnt[j] -= 1 # 计算当前前缀下剩余位置的排列总数 cur = val*(cnt[j]+1)//(n//2-i) if counted+cur >= k: # 超过了k，可以填入 val = cur # 准备下次计算 res += chr(ord('a')+j) break counted += cur # 计入累计排列总数 cnt[j] += 1 if len(res) < n//2: return "" res = res+(s[n//2] if n&1 else '')+res[::-1] # 还原成回文串 return res