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') = 2s 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') = 5Return 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.
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 * 1051 <= k <= s.lengths consists only of lowercase English letters.Sort the characters of the string based on their frequencies in descending order. Select the top k unique characters and compute the beauty by forming all possible k-subsequences using these k characters. The final result is the number of such subsequences with maximum beauty.
We utilize the collections.Counter to count character frequencies. We sort these frequencies, choose the top k, and calculate their sum as maximum beauty. For counting subsequences with maximum beauty, we multiply the combinations of each chosen character's occurrence, which gives us the count of unique sets of k characters resulting in max beauty.
Time Complexity: O(n log n) for sorting the frequencies where n is the number of unique characters in s.
Space Complexity: O(n) for storing character counts and sorted frequencies.
Use character frequency counts to find all unique candidates for k-length subsequences with maximum beauty. Compute the number of such subsequences directly using combinatorial mathematics.
We build a frequency map of characters using a HashMap, sort the frequencies, and select the top k frequencies to calculate maximum beauty. We calculate the number of such k-length subsequences using combination calculations derived from frequencies, providing the desired result.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) due to storage of frequency list and map.
This approach involves first calculating the frequency of each character in the string. Then, we will create all possible k-subsequences using a greedy method that always selects the characters with the highest frequency first.
This Python solution uses a Counter to count frequency of characters. It then sorts these frequencies and selects the k most frequent for the maximum beauty calculation. After calculating max beauty, it computes the number of such subsequences by multiplying the frequencies modulo 10^9 + 7.
Java
Time Complexity: O(n + m log m), where n is the length of the string and m is the number of unique characters. Space Complexity: O(m), to store the frequencies.
This approach focuses on generating combinations of indices that correspond to forming k-subsequences. Using combinatorial counting, it calculates ways to choose indices that contribute to the maximum beauty.
This C++ solution calculates frequency of each character, sorts frequencies in descending order, sums top k frequencies to find max beauty, and computes subsequence count as a product of these frequencies modulo 10^9 + 7.
JavaScript
Time Complexity: O(n + m log m), Space Complexity: O(m), where m is the number of unique characters.
| Approach | Complexity |
|---|---|
| Greedy with Frequency Count | Time Complexity: O(n log n) for sorting the frequencies where n is the number of unique characters in |
| Mathematical Combinatorics | Time Complexity: O(n log n) due to sorting. |
| Greedy with Frequency Counting | Time Complexity: O(n + m log m), where n is the length of the string and m is the number of unique characters. Space Complexity: O(m), to store the frequencies. |
| Combinatorial Selection | Time Complexity: O(n + m log m), Space Complexity: O(m), where m is the number of unique characters. |
Longest Common Subsequence - Dynamic Programming - Leetcode 1143 • NeetCode • 323,891 views views
Watch 9 more video solutions →Practice Count K-Subsequences of a String With Maximum Beauty with our built-in code editor and test cases.
Practice on FleetCode