Skip to content

Latest commit

 

History

History
113 lines (76 loc) · 3.6 KB

2842.count-k-subsequences-of-a-string-with-maximum-beauty.md

File metadata and controls

113 lines (76 loc) · 3.6 KB

题目地址(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:

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)$

主要的时间在于排序。