Watch 8 video solutions for Count K-Subsequences of a String With Maximum Beauty, a hard level problem involving Hash Table, Math, String. This walkthrough by Prakhar Agrawal has 1,893 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |