LeetCode 题解工作台
统计一个字符串的 k 子序列美丽值最大的数目
给你一个字符串 s 和一个整数 k 。 k 子序列 指的是 s 的一个长度为 k 的 子序列 ，且所有字符都是 唯一 的，也就是说每个字符在子序列里只出现过一次。 定义 f(c) 为字符 c 在 s 中出现的次数。 k 子序列的 美丽值 定义为这个子序列中每一个字符 c 的 f(c) 之 和 。 比…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
答案摘要
我们先用哈希表 统计字符串 中每个字符的出现次数，即 表示字符 在字符串 中出现的次数。 由于 子序列是字符串 中一个长度为 的子序列，且字符唯一，因此，如果 中不同字符的个数小于 ，那么不存在 子序列，直接返回 即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个字符串 s 和一个整数 k 。
k 子序列指的是 s 的一个长度为 k 的 子序列 ，且所有字符都是 唯一 的，也就是说每个字符在子序列里只出现过一次。
定义 f(c) 为字符 c 在 s 中出现的次数。
k 子序列的 美丽值 定义为这个子序列中每一个字符 c 的 f(c) 之 和 。
比方说，s = "abbbdd" 和 k = 2 ，我们有：
f('a') = 1,f('b') = 3,f('d') = 2s的部分 k 子序列为："abbbdd"->"ab"，美丽值为f('a') + f('b') = 4"abbbdd"->"ad"，美丽值为f('a') + f('d') = 3"abbbdd"->"bd"，美丽值为f('b') + f('d') = 5
请你返回一个整数，表示所有 k 子序列 里面 美丽值 是 最大值 的子序列数目。由于答案可能很大，将结果对 109 + 7 取余后返回。
一个字符串的子序列指的是从原字符串里面删除一些字符（也可能一个字符也不删除），不改变剩下字符顺序连接得到的新字符串。
注意：
f(c)指的是字符c在字符串s的出现次数，不是在 k 子序列里的出现次数。- 两个 k 子序列如果有任何一个字符在原字符串中的下标不同，则它们是两个不同的子序列。所以两个不同的 k 子序列可能产生相同的字符串。
示例 1：
输入：s = "bcca", k = 2
输出：4
解释：s 中我们有 f('a') = 1 ，f('b') = 1 和 f('c') = 2 。
s 的 k 子序列为：
bcca ，美丽值为 f('b') + f('c') = 3
bcca ，美丽值为 f('b') + f('c') = 3
bcca ，美丽值为 f('b') + f('a') = 2
bcca ，美丽值为 f('c') + f('a') = 3
bcca ，美丽值为 f('c') + f('a') = 3
总共有 4 个 k 子序列美丽值为最大值 3 。
所以答案为 4 。
示例 2：
输入：s = "abbcd", k = 4 输出：2 解释：s 中我们有 f('a') = 1 ，f('b') = 2 ，f('c') = 1 和 f('d') = 1 。 s 的 k 子序列为： abbcd ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5 abbcd ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5 总共有 2 个 k 子序列美丽值为最大值 5 。 所以答案为 2 。
提示：
1 <= s.length <= 2 * 1051 <= k <= s.lengths只包含小写英文字母。
解题思路
方法一：贪心 + 组合数学
我们先用哈希表 统计字符串 中每个字符的出现次数，即 表示字符 在字符串 中出现的次数。
由于 子序列是字符串 中一个长度为 的子序列，且字符唯一，因此，如果 中不同字符的个数小于 ，那么不存在 子序列，直接返回 即可。
否则，要使得 子序列的美丽值最大，我们需要尽可能地让美丽值大的字符尽可能地多地出现在 子序列中。因此，我们可以对 中的值进行倒序排序，得到一个数组 。
我们记数组 第 个字符的出现次数为 ，一共有 个字符出现的次数为 。
那么我们先找出出现次数大于 的字符，将每个字符出现的次数相乘，得到初始答案 ，剩余的需要选取的字符个数更新为 。我们需要从 个字符中选取 个字符，因此答案需要乘上组合数 ，最后再乘上 ，即 。
注意，这里需要用到快速幂，以及取模操作。
时间复杂度 ，空间复杂度 。其中 是字符串的长度，而 是字符集。本题中字符集为小写字母，因此 。
class Solution:
def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
f = Counter(s)
if len(f) < k:
return 0
mod = 10**9 + 7
vs = sorted(f.values(), reverse=True)
val = vs[k - 1]
x = vs.count(val)
ans = 1
for v in vs:
if v == val:
break
k -= 1
ans = ans * v % mod
ans = ans * comb(x, k) * pow(val, k, mod) % mod
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on sorting the character frequencies and computing combinatorial counts, generally O(n + u log u) where u is unique characters. Space complexity is O(u) for the frequency map. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask how you handle ties in character frequencies.
- question_mark
Expect discussion on combinatorial counting with repeated frequency values.
- question_mark
Clarify that every character in a k-subsequence must be unique.
常见陷阱
外企场景- error
Assuming maximum beauty subsequences can include repeated characters.
- error
Miscalculating combinations when multiple characters share the same frequency.
- error
Sorting or selecting frequencies incorrectly leading to undercounting valid subsequences.
进阶变体
外企场景- arrow_right_alt
Find k-subsequences minimizing beauty instead of maximizing.
- arrow_right_alt
Allow subsequences with repeated characters and adjust counting.
- arrow_right_alt
Compute maximum beauty for subsequences of varying lengths simultaneously.