# 2842. 统计一个字符串的 k 子序列美丽值最大的数目

### 题目地址(2842. 统计一个字符串的 k 子序列美丽值最大的数目)

<https://leetcode.cn/problems/count-k-subsequences-of-a-string-with-maximum-beauty/>

### 题目描述

```
给你一个字符串 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') = 2
s 的部分 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 * 105
1 <= k <= s.length
s 只包含小写英文字母。
```

### 前置知识

* 排列组合

### 思路

显然我们应该贪心地使用频率高的，也就是 f(c) 大的 c。

因此一个思路就是从大到小选择 c，由于同一个 c 是不同的方案。因此选择 c 就有 f(c) 种选法。

如果有两个相同频率的，那么方案数就是 f(c) \* f(c)。 如果有 k 个频率相同的，方案数就是 f(c) \*\* k。

如果有 num 个频率相同的要选，但是只能选 k 个，k < num。那么就可以从 num 个先选 k 个，方案数是 C\_{num}^{k}，然后再用上面的计算方法计算。

最后利用乘法原理，将依次选择的方案数乘起来就好了。

### 代码

* 语言支持：Python3

Python3 Code:

```python
class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        MOD = 10 ** 9 + 7
        ans = 1
        cnt = Counter(Counter(s).values())
        for c, num in sorted(cnt.items(), reverse=True):
            # c 是出现次数
            # num 是出现次数为 c 的有多少个
            if num >= k:
                return ans * pow(c, k, MOD) * comb(num, k) % MOD
            ans *= pow(c, num, MOD) * comb(num, num) % MOD
            k -= num
        return 0

```

**复杂度分析**

令 n 为数组长度

* 时间复杂度：$O(nlogn)$
* 空间复杂度：$O(n)$

主要的时间在于排序。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2842.count-k-subsequences-of-a-string-with-maximum-beauty.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.