class Solution {
public:
int countKSubsequencesWithMaxBeauty(string s, int k) {
}
};
2842. 统计一个字符串的 k 子序列美丽值最大的数目
给你一个字符串 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 子序列里的出现次数。
示例 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 只包含小写英文字母。原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 6.2 MB, 提交时间: 2023-09-04 10:10:16
const mod = 1_000_000_007
func countKSubsequencesWithMaxBeauty(s string, k int) int {
cnt := [26]int{}
for _, b := range s {
cnt[b-'a']++
}
cc := map[int]int{}
for _, c := range cnt {
if c > 0 {
cc[c]++
}
}
type KV struct{ cnt, num int }
kv := make([]KV, 0, len(cc))
for k, v := range cc {
kv = append(kv, KV{k, v})
}
sort.Slice(kv, func(i, j int) bool { return kv[i].cnt > kv[j].cnt })
ans := 1
for _, p := range kv {
if p.num >= k {
return ans * pow(p.cnt, k) % mod * comb(p.num, k) % mod
}
ans = ans * pow(p.cnt, p.num) % mod
k -= p.num
}
return 0 // k 太大，无法选 k 个不一样的字符
}
func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
// 适用于 n 比较小的场景（本题至多 26）
func comb(n, k int) int {
res := n
for i := 2; i <= k; i++ {
res = res * (n - i + 1) / i // n,n-1,n-2,... 中的前 i 个数至少有一个因子 i
}
return res % mod
}
cpp 解法, 执行用时: 32 ms, 内存消耗: 12.2 MB, 提交时间: 2023-09-04 10:10:02
class Solution {
const long long MOD = 1e9 + 7;
long long pow(long long x, int n) {
long long res = 1;
for (; n; n /= 2) {
if (n % 2) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
// 适用于 n 比较小的场景（本题至多 26）
long long comb(long long n, int k) {
auto res = n;
for (int i = 2; i <= k; i++)
res = res * --n / i; // n,n-1,n-2,... 中的前 i 个数至少有一个因子 i
return res % MOD;
}
public:
int countKSubsequencesWithMaxBeauty(string s, int k) {
int cnt[26]{};
for (char c: s)
cnt[c - 'a']++;
map<int, int> cc;
for (int c: cnt)
if (c) cc[-c]++; // -c 方便从大到小遍历
long long ans = 1;
for (auto [c, num]: cc) {
if (num >= k)
return ans * pow(-c, k) % MOD * comb(num, k) % MOD;
ans = ans * pow(-c, num) % MOD;
k -= num;
}
return 0; // k 太大，无法选 k 个不一样的字符
}
};
java 解法, 执行用时: 8 ms, 内存消耗: 44.4 MB, 提交时间: 2023-09-04 10:09:45
class Solution {
private static final long MOD = (long) 1e9 + 7;
public int countKSubsequencesWithMaxBeauty(String s, int k) {
var cnt = new int[26];
for (char c : s.toCharArray())
cnt[c - 'a']++;
var cc = new TreeMap<Integer, Integer>();
for (int c : cnt)
if (c > 0)
cc.merge(c, 1, Integer::sum);
long ans = 1;
for (var e : cc.descendingMap().entrySet()) {
int c = e.getKey(), num = e.getValue();
if (num >= k)
return (int) (ans * pow(c, k) % MOD * comb(num, k) % MOD);
ans = ans * pow(c, num) % MOD;
k -= num;
}
return 0; // k 太大，无法选 k 个不一样的字符
}
private long pow(long x, int n) {
long res = 1;
for (; n > 0; n /= 2) {
if (n % 2 > 0)
res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
// 适用于 n 比较小的场景（本题至多 26）
private long comb(long n, int k) {
long res = n;
for (int i = 2; i <= k; i++)
res = res * --n / i; // n,n-1,n-2,... 中的前 i 个数至少有一个因子 i
return res % MOD;
}
}
python3 解法, 执行用时: 88 ms, 内存消耗: 17 MB, 提交时间: 2023-09-04 10:09:26
# 组合数学
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):
if num >= k:
return ans * pow(c, k, MOD) * comb(num, k) % MOD
ans *= pow(c, num, MOD)
k -= num
return 0 # k 太大，无法选 k 个不一样的字符