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.Problem Overview: Given a string s and integer k, count the number of distinct k-subsequences that achieve the maximum possible beauty. Beauty is defined as the sum of frequencies of the chosen characters in the original string. The challenge is selecting the best k distinct characters and counting how many subsequences can be formed.
Approach 1: Greedy with Frequency Count (O(n + m log m) time, O(m) space)
Start by counting character frequencies using a hash table. Sort the frequencies in descending order and select the top k characters to maximize beauty. The number of valid subsequences equals the product of the frequencies of the chosen characters. When multiple characters share the same frequency at the boundary, combinations are required to count how many ways you can pick them. This approach relies on a simple greedy rule: always prioritize characters with the highest frequency.
Approach 2: Mathematical Combinatorics (O(n + m log m) time, O(m) space)
After computing frequencies, sort them and determine the cutoff frequency for the k-th character. All characters with higher frequency must be chosen. For characters with the same cutoff frequency, compute how many need to be selected and apply combinatorial math C(n, r). Multiply this by the frequency contributions to count subsequences. This approach leverages combinatorics to efficiently handle ties without enumerating subsets.
Approach 3: Greedy with Frequency Counting (Optimized) (O(n + m log m) time, O(m) space)
Count frequencies and store them in an array. Sort descending and iterate through the largest values while tracking how many characters are used. If a frequency group exceeds the remaining slots, compute combinations only for that group. Multiplying contributions with modular arithmetic avoids overflow. The greedy decision works because maximizing beauty always means choosing the highest-frequency characters first.
Approach 4: Combinatorial Selection with Frequency Groups (O(n + m log m) time, O(m) space)
Group characters by frequency and process them from highest to lowest. Maintain remaining selections and accumulate subsequence counts using combinatorial selection. Instead of treating characters individually, operate on frequency groups, which simplifies tie handling and reduces repeated calculations. The logic combines greedy ordering with precise combinatorial counting.
Recommended for interviews: The greedy frequency approach combined with combinatorics is what most interviewers expect. It shows you understand why choosing the highest-frequency characters maximizes beauty and how to correctly count combinations when multiple characters share the same frequency.
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.
Python
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.
Java
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.
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.
C++
JavaScript
Time Complexity: O(n + m log m), Space Complexity: O(m), where m is the number of unique characters.
First, we use a hash table f to count the occurrence of each character in the string s, i.e., f[c] represents the number of times character c appears in the string s.
Since a k-subsequence is a subsequence of length k in the string s with unique characters, if the number of different characters in f is less than k, then there is no k-subsequence, and we can directly return 0.
Otherwise, to maximize the beauty value of the k-subsequence, we need to make characters with high beauty values appear as much as possible in the k-subsequence. Therefore, we can sort the values in f in reverse order to get an array vs.
We denote the occurrence of the kth character in the array vs as val, and there are x characters with an occurrence of val.
Then we first find out the characters with occurrences greater than val, multiply the occurrences of each character to get the initial answer ans, and update the remaining number of characters to be selected to k. We need to select k characters from x characters, so the answer needs to be multiplied by the combination number C_x^k, and finally multiplied by val^k, i.e., ans = ans times C_x^k times val^k.
Note that we need to use fast power and modulo operations here.
The time complexity is O(n), and the space complexity is O(|\Sigma|). Here, n is the length of the string, and \Sigma is the character set. In this problem, the character set is lowercase letters, so |\Sigma| = 26.
Python
Java
C++
Go
TypeScript
| 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. |
| Greedy + Combinatorial Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Frequency Count | O(n + m log m) | O(m) | General solution; simple greedy logic with sorted frequencies |
| Mathematical Combinatorics | O(n + m log m) | O(m) | Best when handling many equal-frequency characters |
| Greedy with Frequency Counting (Optimized) | O(n + m log m) | O(m) | Interview-friendly approach combining greedy selection and modular multiplication |
| Combinatorial Selection by Frequency Groups | O(n + m log m) | O(m) | Useful when implementing grouped frequency counting for cleaner tie handling |
Leetcode BiWeekly contest 112 - Hard - Count K-Subsequences of a String With Maximum Beauty • Prakhar Agrawal • 1,893 views views
Watch 7 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