题目描述

给你一个字符串 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 子序列 里面 美丽值 是 最大值 的子序列数目。由于答案可能很大，将结果对 10^9 + 7 取余后返回。

一个字符串的子序列指的是从原字符串里面删除一些字符（也可能一个字符也不删除），不改变剩下字符顺序连接得到的新字符串。

注意：

• f(c) 指的是字符 c 在字符串 s 的出现次数，不是在 k 子序列里的出现次数。
• 两个 k 子序列如果有任何一个字符在原字符串中的下标不同，则它们是两个不同的子序列。所以两个不同的 k 子序列可能产生相同的字符串。

样例

输入：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(c)(a)，美丽值为 f('c') + f('a') = 3
总共有 4 个 k 子序列美丽值为最大值 3。
所以答案为 4。

输入：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 * 10^5
• 1 <= k <= s.length
• s 只包含小写英文字母。

算法

(数学，乘法原理，乘法逆元) $O(|\Sigma| \log |\Sigma| + n \log n)$

1. 显然，按照出现次数 $f$ 从大到小分别取字符，可以得到美丽值最大的子序列。
2. 求出每个字符的出现次数，然后从大到小排序。
3. 初始化答案为 $1$，然后按顺序遍历一组出现次数相同的字符，假设这一组字符出现次数为 $f(i)$，共有 $cnt$ 个，分一下两种情况讨论：
   1. $k \ge cnt$，这时这一组字符必定是每种字符取一个，根据乘法原理，答案乘 $f(i)^{cnt}$，然后 $k$ 减去 $cnt$。
   2. $k < cnt$，这时需要从 $cnt$ 种字符中，需要取 $k$ 个不同的字符，根据乘法原理和组合数，答案需要乘 $f(i)^k \cdot C(cnt, k)$，然后 $k$ 置 $0$ 结束遍历。
4. 计算组合数时，需要用到乘法逆元。
5. 注意，最后如果 $k$ 不为 $0$，则说明不同数字的种类数不足 $k$ 个，答案为 $0$。

时间复杂度

• 遍历字符串统计每个字符的出现次数的时间复杂度为 $O(n)$。
• 排序出现次数数组的时间复杂度为 $O(|\Sigma| \log |\Sigma|)$，其中 $|\Sigma|$ 为字符集的大小。
• 累计答案的时间瓶颈在于计算组合数，时间复杂度为 $O(n \log n)$。
• 故总时间复杂度为 $O(|\Sigma| \log |\Sigma| + n \log n)$。

空间复杂度

• 需要 $O(|\Sigma|)$ 的额外空间存储出现次数数组和排序出现次数数组的系统栈空间。

C++ 代码

#define LL long long

const int mod = 1000000007;

class Solution {
private:
    int power(int x, int y) {
        LL res = 1, p = x;
        for (; y; y >>= 1) {
            if (y & 1) res = res * p % mod;
            p = p * p % mod;
        }

        return res;
    }

    int C(int x, int y) {
        LL res = 1;
        for (int i = 1; i <= x; i++)
            res = res * i % mod;

        for (int i = 1; i <= x - y; i++)
            res = res * power(i, mod - 2) % mod;

        for (int i = 1; i <= y; i++)
            res = res * power(i, mod - 2) % mod;

        return res;
    }

public:
    int countKSubsequencesWithMaxBeauty(string s, int k) {
        const int n = s.size();
        vector<int> f(26, 0);

        for (char c : s)
            ++f[c - 'a'];

        sort(f.begin(), f.end(), [](int x, int y) {
            return x > y;
        });

        LL ans = 1;
        for (int i = 0, cnt = 0; i < 26 && k > 0; i++) {
            ++cnt;
            if (i < 25 && f[i] == f[i + 1])
                continue;

            ans = ans * power(f[i], min(cnt, k)) % mod;

            if (k >= cnt) {
                k -= cnt;
            } else {
                ans = ans * C(cnt, k) % mod;
                k = 0;
            }

            cnt = 0;
        }

        if (k > 0)
            return 0;

        return ans;
    }
};