Count K-Subsequences of a String With Maximum Beauty - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
2842. Count K-Subsequences of a String With Maximum Beauty
Hard
50 Points
Hash Table
Math
String
Greedy
Combinatorics
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:
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
Examples
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.
2842. Count K-Subsequences of a String With Maximum Beauty
Hard
50 Points
Hash Table
Math
String
Greedy
Combinatorics
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:
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
Examples
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.