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

You are given a string s and an integer k.

A k-subsequence is a subsequence of s, having length k, and all its characters are unique, i.e., every character occurs once.

Let f(c) denote the number of times the character c occurs in s.

The beauty of a k-subsequence is the sum of f(c) for every character c in the k-subsequence.

For example, consider s = "abbbdd" and k = 2:

• f('a') = 1, f('b') = 3, f('d') = 2
• Some k-subsequences of s are:
  • "abbbdd" -> "ab" having a beauty of f('a') + f('b') = 4
  • "abbbdd" -> "ad" having a beauty of f('a') + f('d') = 3
  • "abbbdd" -> "bd" having a beauty of f('b') + f('d') = 5

Return an integer denoting the number of k-subsequences whose beauty is the maximum among all k-subsequences. Since the answer may be too large, return it modulo 109 + 7.

A subsequence of a string is a new string formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

Notes

• f(c) is the number of times a character c occurs in s, not a k-subsequence.
• Two k-subsequences are considered different if one is formed by an index that is not present in the other. So, two k-subsequences may form the same string.

 

Example 1:

Input: s = "bcca", k = 2
Output: 4
Explanation: From s we have f('a') = 1, f('b') = 1, and f('c') = 2.
The k-subsequences of s are: 
bcca having a beauty of f('b') + f('c') = 3 
bcca having a beauty of f('b') + f('c') = 3 
bcca having a beauty of f('b') + f('a') = 2 
bcca having a beauty of f('c') + f('a') = 3
bcca having a beauty of f('c') + f('a') = 3 
There are 4 k-subsequences that have the maximum beauty, 3. 
Hence, the answer is 4. 

Example 2:

Input: s = "abbcd", k = 4
Output: 2
Explanation: From s we have f('a') = 1, f('b') = 2, f('c') = 1, and f('d') = 1. 
The k-subsequences of s are: 
abbcd having a beauty of f('a') + f('b') + f('c') + f('d') = 5
abbcd having a beauty of f('a') + f('b') + f('c') + f('d') = 5 
There are 2 k-subsequences that have the maximum beauty, 5. 
Hence, the answer is 2. 

 

Constraints:

• 1 <= s.length <= 2 * 105
• 1 <= k <= s.length
• s consists only of lowercase English letters.

/*
 * Java Stream Approach:
 * The problem can be solved using a similar approach as above but with streams.
 * 1. Calculate character frequencies.
 * 2. Filter and sort them using streams.
 * 3. Sum the largest 'k' values for the maximum beauty value.
 * 4. Count the occurrences of this maximum value.
 */
import java.util.*;
import java.util.stream.*;

public class SolutionStream {
    private static final int MOD = 1000000007;

    public int maxBeautySubsequences(String s, int k) {
        int[] freq = new int[26];
        s.chars().forEach(c -> freq[c - 'a']++);

        int[] sortedFreq = Arrays.stream(freq)
                .filter(f -> f > 0)
                .boxed()
                .sorted(Collections.reverseOrder())
                .mapToInt(Integer::intValue)
                .toArray();

        long maxBeauty = 0;
        long maxBeautyCount = 0;
        for (int i = 0; i <= sortedFreq.length - k; i++) {
            long beauty = IntStream.range(i, i + k).mapToLong(j -> sortedFreq[j]).sum();
            if (beauty > maxBeauty) {
                maxBeauty = beauty;
                maxBeautyCount = 1;
            } else if (beauty == maxBeauty) {
                maxBeautyCount++;
            }
        }
        return (int) (maxBeautyCount % MOD);
    }
}

这个题解首先通过计算每个字符在字符串中的出现次数，然后进一步统计每个出现次数的字符有多少个。接着，从出现次数最高的字符开始，尝试构建长度为k的子序列，计算其美丽值。如果某个出现次数的字符数量足以构成长度k的子序列，那么直接计算该子序列的美丽值并返回。如果不足以构成长度k，就将这些字符的美丽值加入总和，并减少k的值，继续寻找下一组出现次数较多的字符。这种方法保证了在满足子序列长度为k的条件下，尽可能地使用出现次数高的字符，从而最大化子序列的美丽值。

O(u log u) 其中 u 是不同出现次数的数量

O(u) 其中 u 是不同出现次数的数量