2842. Count K-Subsequences of a String With Maximum Beauty Hard

1/**
2 * [2842] Count K-Subsequences of a String With Maximum Beauty
3 *
4 * You are given a string s and an integer k.
5 * A k-subsequence is a subsequence of s, having length k, and all its characters are unique, i.e., every character occurs once.
6 * Let f(c) denote the number of times the character c occurs in s.
7 * The beauty of a k-subsequence is the sum of f(c) for every character c in the k-subsequence.
8 * For example, consider s = "abbbdd" and k = 2:
9 * 
10 * 	f('a') = 1, f('b') = 3, f('d') = 2
11 * 	Some k-subsequences of s are:
12 * 	
13 * 		"<u>ab</u>bbdd" -> "ab" having a beauty of f('a') + f('b') = 4
14 * 		"<u>a</u>bbb<u>d</u>d" -> "ad" having a beauty of f('a') + f('d') = 3
15 * 		"a<u>b</u>bb<u>d</u>d" -> "bd" having a beauty of f('b') + f('d') = 5
16 * 	
17 * 	
18 * 
19 * 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 10^9 + 7.
20 * 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.
21 * Notes
22 * 
23 * 	f(c) is the number of times a character c occurs in s, not a k-subsequence.
24 * 	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.
25 * 
26 *  
27 * <strong class="example">Example 1:
28 * 
29 * Input: s = "bcca", k = 2
30 * Output: 4
31 * Explanation: <span style="white-space: normal">From s we have f('a') = 1, f('b') = 1, and f('c') = 2.</span>
32 * The k-subsequences of s are: 
33 * <u>bc</u>ca having a beauty of f('b') + f('c') = 3 
34 * <u>b</u>c<u>c</u>a having a beauty of f('b') + f('c') = 3 
35 * <u>b</u>cc<u>a</u> having a beauty of f('b') + f('a') = 2 
36 * b<u>c</u>c<u>a</u> having a beauty of f('c') + f('a') = 3
37 * bc<u>ca</u> having a beauty of f('c') + f('a') = 3 
38 * There are 4 k-subsequences that have the maximum beauty, 3. 
39 * Hence, the answer is 4. 
40 * 
41 * <strong class="example">Example 2:
42 * 
43 * Input: s = "abbcd", k = 4
44 * Output: 2
45 * Explanation: From s we have f('a') = 1, f('b') = 2, f('c') = 1, and f('d') = 1. 
46 * The k-subsequences of s are: 
47 * <u>ab</u>b<u>cd</u> having a beauty of f('a') + f('b') + f('c') + f('d') = 5
48 * <u style="white-space: normal;">a</u>b<u>bcd</u> having a beauty of f('a') + f('b') + f('c') + f('d') = 5 
49 * There are 2 k-subsequences that have the maximum beauty, 5. 
50 * Hence, the answer is 2. 
51 * 
52 *  
53 * Constraints:
54 * 
55 * 	1 <= s.length <= 2 * 10^5
56 * 	1 <= k <= s.length
57 * 	s consists only of lowercase English letters.
58 * 
59 */
60pub struct Solution {}
61
62// problem: https://leetcode.com/problems/count-k-subsequences-of-a-string-with-maximum-beauty/
63// discuss: https://leetcode.com/problems/count-k-subsequences-of-a-string-with-maximum-beauty/discuss/?currentPage=1&orderBy=most_votes&query=
64
65// submission codes start here
66
67impl Solution {
68    pub fn count_k_subsequences_with_max_beauty(s: String, k: i32) -> i32 {
69        0
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_2842() {
81    }
82}
83