Count K-Subsequences of a String With Maximum Beauty - Solution & Explanation
Problem Statement
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
sare:"abbbdd"->"ab"having a beauty off('a') + f('b') = 4"abbbdd"->"ad"having a beauty off('a') + f('d') = 3"abbbdd"->"bd"having a beauty off('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 charactercoccurs ins, 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 * 1051 <= k <= s.lengthsconsists only of lowercase English letters.
Approach Overview
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.
Approach 1: Greedy with Frequency Count
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.
Code
Python
Complexity
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.
Approach 2: Mathematical Combinatorics
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.
Code
Java
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) due to storage of frequency list and map.
Approach 3: Greedy with Frequency Counting
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.
Complexity
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.
Approach 4: Combinatorial Selection
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.
Code
C++
JavaScript
Complexity
Time Complexity: O(n + m log m), Space Complexity: O(m), where m is the number of unique characters.
Approach 5: Greedy + Combinatorial Mathematics
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode BiWeekly contest 112 - Hard - Count K-Subsequences of a String With Maximum Beauty • Prakhar Agrawal • 1,895 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Count K-Subsequences of a String With Maximum Beauty easy or hard?
Count K-Subsequences of a String With Maximum Beauty Python/Java solution
How to solve Count K-Subsequences of a String With Maximum Beauty in O(n)?
What is the best approach for Count K-Subsequences of a String With Maximum Beauty?
Is Count K-Subsequences of a String With Maximum Beauty asked at Google/Amazon/Meta?
What data structure is used in Count K-Subsequences of a String With Maximum Beauty?
What is the time complexity of Count K-Subsequences of a String With Maximum Beauty?
Ready to solve this problem?
Practice Count K-Subsequences of a String With Maximum Beauty with our built-in code editor and test cases.
Practice on FleetCode