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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:07 2023-09-13 17:01:07 Updated    

给你一个字符串 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 子序列为：
    • " _ **ab**_ bbdd" -> "ab" ，美丽值为 f('a') + f('b') = 4
    • " _ **a**_ bbb _ **d**_ d" -> "ad" ，美丽值为 f('a') + f('d') = 3
    • "a _ **b**_ bb _ **d**_ d" -> "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 子序列为：
_**bc**_ ca ，美丽值为 f('b') + f('c') = 3
_**b**_ c _ **c**_ a ，美丽值为 f('b') + f('c') = 3
_**b**_ cc _ **a**_ ，美丽值为 f('b') + f('a') = 2
b _ **c**_ c _ **a**_ **** ，美丽值为 f('c') + f('a') = 3
bc _ **ca**_ ，美丽值为 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 子序列为：
_**ab**_ b _ **cd**_ ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5
**_a_** b _ **bcd**_ ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5 
总共有 2 个 k 子序列美丽值为最大值 5 。
所以答案为 2 。

提示：

  • 1 <= s.length <= 2 * 105
  • 1 <= k <= s.length
  • s 只包含小写英文字母。

请看 视频讲解 第四题。

提示 1

思考：k=1 要怎么做？

从出现次数最多的字符中选一个字母。

提示 2

思考：k=2 要怎么做？

从出现次数最多的开始选，如果有多个出现次数最多的呢？

例如 s=\texttt{aaaabbbbcccc},\ k=2，那么需要从 3 种字母中选 k 种，每种都有 4 个字符可以选（题目说相同字符组成的子序列也算不同的），所以方案数为

4^k \cdot C_3^k

提示 3

统计每个字符出现次数的个数，然后从大到小遍历次数 c 及其个数 num。

  • 如果 num}<k，那么这 c 种字符每种选一个，方案数为 c^{\textit{num}，然后将 k 减去 num。
  • 如果 num}\ge k，根据上面的讨论，方案数为 c^k\cdot C_{\textit{num} }^k。

所有方案数相乘即为答案。

如果 k 太大（循环中没有出现 num}\ge k），那么不存在合法子序列，返回 0。

有关模运算的小知识见文末的讲解。

代码中用到了快速幂，请看 50. Pow(x, n) 。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
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 个不一样的字符
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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 和 k 都比较小的场景（本题至多 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;
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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 和 k 都比较小的场景（本题至多 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 个不一样的字符
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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 和 k 都比较小的场景（本题至多 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
}

复杂度分析

  • 时间复杂度：\mathcal{O}(n)，其中 n 为 s 的长度。时间主要用在遍历字符串 s 上了。
  • 空间复杂度：\mathcal{O}(|\Sigma|)。其中 |\Sigma| 为字符集合的大小，本题中字符均为小写字母，所以 |\Sigma|=26。

算法小课堂：模运算

如果让你计算 1234\cdot 6789 的个位数，你会如何计算？

由于只有个位数会影响到乘积的个位数，那么 4\cdot 9=36 的个位数 6 就是答案。

对于 1234+6789 的个位数，同理，4+9=13 的个位数 3 就是答案。

你能把这个结论抽象成数学等式吗？

一般地，涉及到取模的题目，通常会用到如下等式（上面计算的是 m=10）：

(a+b)\bmod m = ((a\bmod m) + (b\bmod m)) \bmod m

(a\cdot b) \bmod m=((a\bmod m)\cdot (b\bmod m)) \bmod m

证明：根据带余除法，任意整数 a 都可以表示为 a=km+r，这里 r 相当于 a\bmod m。那么设 a=k_1m+r_1,\ b=k_2m+r_2。

第一个等式：

\begin{aligned}
&\ (a+b) \bmod m\
=&\ ((k_1+k_2) m+r_1+r_2)\bmod m\
=&\ (r_1+r_2)\bmod m\
=&\ ((a\bmod m) + (b\bmod m)) \bmod m
\end{aligned}

第二个等式：

\begin{aligned}
&\ (a\cdot b) \bmod m\
=&\ (k_1k_2m^2+(k_1r_2+k_2r_1)m+r_1r_2)\bmod m\
=&\ (r_1r_2)\bmod m\
=&\ ((a\bmod m)\cdot (b\bmod m)) \bmod m
\end{aligned}

根据这两个恒等式，可以随意地对代码中的加法和乘法的结果取模。

 Comments
On this page
2842-统计一个字符串的 k 子序列美丽值最大的数目
  1. 提示 1
  2. 提示 2
  3. 提示 3
  4. 算法小课堂：模运算