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

k 子序列指的是 s 的一个长度为 k 的 子序列 ，且所有字符都是唯一的，也就是说每个字符在子序列里只出现过一次。
定义 f(c) 为字符 c 在 s 中出现的次数。
k 子序列的 美丽值定义为这个子序列中每一个字符 c 的f(c)之和

1. 贪心 + 组合枚举

贪心选美丽值最大的字符，对于最后美丽值相同的，进行组合计算

class Solution {
public:
    const int MOD = 1e9 + 7;
    int countKSubsequencesWithMaxBeauty(string s, int k) {
        vector<int> dp(26);
        for(int i=0;i<s.size();i++)
            dp[s[i]-'a']++;
        sort(dp.begin(),dp.end());
        if(k>26||dp[26-k]==0) return 0;
        //要使得最大，序列中最小的数进行任意组合
        long long res = 1;
        int target = dp[26-k];//最小的值
        auto start = lower_bound(dp.begin(),dp.end(),target);
        auto end = upper_bound(dp.begin(),dp.end(),target);
        vector<int> combo(start,end); 
        int m = k - (dp.end() - end); //最小的数里面选m个
        for(int i=25;i>=26-(k-m);i--)  //后面的数选k-m个
            res = (res * dp[i])%MOD;
        //从combo中选出m个数组合
        long long rest = 0;
        for(int mask=0;mask<(1<<combo.size());mask++){
            if(__builtin_popcount(mask)==m){
                long long cur = 1;
                for(int i=0;i<combo.size();i++)
                     if ((mask >> i) & 1) cur = (cur * combo[i])%MOD;
                rest += cur;
            }
        }
        res = (res * (rest%MOD))%MOD;
        return  res;
    }
};