2842. 具有最大美丽值的字符串的 K 子序列数量

Hard

题目描述

给你一个字符串 s 和一个整数 k。

k 子序列是 s 的一个子序列，长度为 k，且所有字符都是唯一的，即每个字符只出现一次。

设 f(c) 表示字符 c 在 s 中出现的次数。

k 子序列的美丽值是该 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 子序列中美丽值最大的子序列数量。由于答案可能很大，返回对 10^9 + 7 取模的结果。

子序列是通过删除原字符串中的某些（可能为零）字符而形成的新字符串，且不改变剩余字符的相对位置。

注意：

f(c) 是字符 c 在 s 中的出现次数，而不是在 k 子序列中的出现次数。
如果两个 k 子序列由不同的索引组成，则认为它们是不同的。因此，两个 k 子序列可能形成相同的字符串。

示例 1：

输入：s = "bcca", k = 2
输出：4
解释：从 s 中我们有 f('a') = 1, f('b') = 1, f('c') = 2。
最大美丽值为 3，有 4 个 k 子序列达到这个值。

示例 2：

输入：s = "abbcd", k = 4
输出：2
解释：从 s 中我们有 f('a') = 1, f('b') = 2, f('c') = 1, f('d') = 1。
最大美丽值为 5，有 2 个 k 子序列达到这个值。

约束条件：

1 <= s.length <= 2 * 10^5
1 <= k <= s.length
s 仅由小写英文字母组成

解题思路

这道题的核心是贪心策略：要使 k 子序列的美丽值最大，我们应该选择频次最高的 k 个不同字符。

分析步骤：

统计字符频次：首先统计每个字符在字符串中的出现次数。
贪心选择：为了获得最大美丽值，我们需要选择频次最高的 k 个不同字符。如果字符种类数少于 k，则无法构成有效的 k 子序列。
计算方案数：对于选定的字符集合，我们需要计算有多少种方式来选择这些字符的位置。关键观察是：
- 对于频次相同的字符，我们可能需要从中选择部分字符
- 对于频次为 f 的字符 c，如果选择它，那么有 f 种方式选择该字符在字符串中的位置
处理频次相同的情况：当存在多个相同频次的字符时，需要考虑组合数学。如果有 cnt 个频次为 f 的字符，我们需要从中选择 need 个，方案数为 C(cnt, need) × f^need。
模运算：由于结果可能很大，需要在计算过程中进行模运算。

算法流程：

统计字符频次并按频次降序排序
贪心选择频次最高的 k 个字符
对于频次相同的字符群组，使用组合数学计算方案数
累乘得到最终结果

代码实现

class Solution {
public:
    static const int MOD = 1000000007;
    
    long long power(long long base, long long exp, long long mod) {
        long long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }
    
    long long combination(int n, int r) {
        if (r > n || r < 0) return 0;
        if (r == 0 || r == n) return 1;
        
        long long num = 1, den = 1;
        for (int i = 0; i < r; i++) {
            num = (num * (n - i)) % MOD;
            den = (den * (i + 1)) % MOD;
        }
        return (num * power(den, MOD - 2, MOD)) % MOD;
    }
    
    int countKSubsequencesWithMaxBeauty(string s, int k) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        if (freq.size() < k) return 0;
        
        vector<int> frequencies;
        for (auto& p : freq) {
            frequencies.push_back(p.second);
        }
        sort(frequencies.rbegin(), frequencies.rend());
        
        long long result = 1;
        int selected = 0;
        
        for (int i = 0; i < frequencies.size() && selected < k; ) {
            int currentFreq = frequencies[i];
            int count = 0;
            
            while (i < frequencies.size() && frequencies[i] == currentFreq) {
                count++;
                i++;
            }
            
            int need = min(count, k - selected);
            
            long long ways = combination(count, need);
            long long positions = power(currentFreq, need, MOD);
            
            result = (result * ways) % MOD;
            result = (result * positions) % MOD;
            
            selected += need;
        }
        
        return result;
    }
};

class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        MOD = 10**9 + 7
        
        def power(base, exp, mod):
            result = 1
            base %= mod
            while exp > 0:
                if exp & 1:
                    result = (result * base) % mod
                base = (base * base) % mod
                exp >>= 1
            return result
        
        def combination(n, r):
            if r > n or r < 0:
                return 0
            if r == 0 or r == n:
                return 1
            
            num = den = 1
            for i in range(r):
                num = (num * (n - i)) % MOD
                den = (den * (i + 1)) % MOD
            
            return (num * power(den, MOD - 2, MOD)) % MOD
        
        from collections import Counter
        freq = Counter(s)
        
        if len(freq) < k:
            return 0
        
        frequencies = sorted(freq.values(), reverse=True)
        
        result = 1
        selected = 0
        i = 0
        
        while i < len(frequencies) and selected < k:
            current_freq = frequencies[i]
            count = 0
            
            while i < len(frequencies) and frequencies[i] == current_freq:
                count += 1
                i += 1
            
            need = min(count, k - selected)
            
            ways = combination(count, need)
            positions = power(current_freq, need, MOD)
            
            result = (result * ways) % MOD
            result = (result * positions) % MOD
            
            selected += need
        
        return result

public class Solution {
    private const int MOD = 1000000007;
    
    private long Power(long baseNum, long exp, long mod) {
        long result = 1;
        baseNum %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * baseNum) % mod;
            }
            baseNum = (baseNum * baseNum) % mod;
            exp /= 2;
        }
        return result;
    }
    
    private long Combination(int n, int r) {
        if (r > n || r < 0) return 0;
        if (r == 0 || r == n) return 1;
        
        long num = 1, den = 1;
        for (int i = 0; i < r; i++) {
            num = (num * (n - i)) % MOD;
            den = (den * (i + 1)) % MOD;
        }
        return (num * Power(den, MOD - 2, MOD)) % MOD;
    }
    
    public int CountKSubsequencesWithMaxBeauty(string s, int k) {
        var freq = new Dictionary<char, int>();
        foreach (char c in s) {
            freq[c] = freq.GetValueOrDefault(c, 0) + 1;
        }
        
        if (freq.Count < k) return 0;
        
        var frequencies = freq.Values.ToList();
        frequencies.Sort((a, b) => b.CompareTo(a));
        
        long result = 1;
        int selected = 0;
        int i = 0;
        
        while (i < frequencies.Count && selected < k) {
            int currentFreq = frequencies[i];
            int count = 0;
            
            while (i < frequencies.Count && frequencies[i] == currentFreq) {
                count++;
                i++;
            }
            
            int need = Math.Min(count, k - selected);
            
            long ways = Combination(count, need);
            long positions = Power(currentFreq, need, MOD);
            
            result = (result * ways) % MOD;
            result = (result * positions) % MOD;
            
            selected += need;
        }
        
        return (int)result;
    }
}

var countKSubsequencesWithMaxBeauty = function(s, k) {
    const MOD = 1000000007;
    
    // Count frequency of each character
    const freq = {};
    for (let char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    
    // Get unique frequencies and sort them in descending order
    const frequencies = Object.values(freq).sort((a, b) => b - a);
    
    // If we don't have enough unique characters
    if (frequencies.length < k) return 0;
    
    // Find the k-th largest frequency (minimum frequency in our selection)
    const minFreq = frequencies[k - 1];
    
    // Count how many characters have frequency > minFreq
    let higherCount = 0;
    let equalCount = 0;
    
    for (let f of frequencies) {
        if (f > minFreq) higherCount++;
        else if (f === minFreq) equalCount++;
    }
    
    // We need to select (k - higherCount) characters from equalCount characters with minFreq
    const needFromEqual = k - higherCount;
    
    if (needFromEqual > equalCount) return 0;
    
    // Calculate combinations C(equalCount, needFromEqual)
    function combination(n, r) {
        if (r > n || r < 0) return 0;
        if (r === 0 || r === n) return 1;
        
        let result = 1;
        for (let i = 0; i < r; i++) {
            result = (result * (n - i)) % MOD;
            result = (result * modInverse(i + 1)) % MOD;
        }
        return result;
    }
    
    function modInverse(a) {
        return modPow(a, MOD - 2);
    }
    
    function modPow(base, exp) {
        let result = 1;
        while (exp > 0) {
            if (exp % 2 === 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp = Math.floor(exp / 2);
        }
        return result;
    }
    
    // Calculate the result
    let result = combination(equalCount, needFromEqual);
    
    // Multiply by minFreq^needFromEqual for characters with minFreq
    result = (result * modPow(minFreq, needFromEqual)) % MOD;
    
    // Multiply by frequency for each character with higher frequency
    for (let f of frequencies) {
        if (f > minFreq) {
            result = (result * f) % MOD;
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(n + m log m)
空间复杂度	O(m)

其中 n 是字符串长度，m 是不同字符的数量（最多26个）。时间复杂度主要来自统计字符频次和排序频次数组。

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

解题思路

代码实现

复杂度分析

相关题目