#2842

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Count K-Subsequences of a String With Maximum Beauty

Determine the number of k-length unique subsequences in a string that maximize the sum of character frequencies efficiently using greedy methods.

hash table math string greedy combinatorics

Problem Statement

Given a string s consisting of lowercase English letters and an integer k, find all subsequences of length k where each character is unique. Define the beauty of a k-subsequence as the sum of frequencies of its characters in s.

Return the number of k-subsequences with the maximum possible beauty. For example, consider s = "bcca" and k = 2: compute f(c) for each character, then count the subsequences that achieve the highest sum of f(c) values.

Examples

Example 1

Input: s = "bcca", k = 2

Output: 4

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

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.

Solution Approach

Count Character Frequencies

Use a hash table to count occurrences of each character in s. This frequency map f(c) is essential for evaluating subsequence beauty.

Greedy Selection of Top Frequencies

Sort characters by frequency in descending order and select the top k characters to maximize beauty. The greedy choice ensures each selected character contributes the most to the sum.

Combinatorial Counting

Calculate the number of unique k-subsequences using combinations of indices for characters with the same frequency, carefully handling repeated frequencies to avoid overcounting.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on sorting the character frequencies and computing combinatorial counts, generally O(n + u log u) where u is unique characters. Space complexity is O(u) for the frequency map.

What Interviewers Usually Probe

They may ask how you handle ties in character frequencies.
Expect discussion on combinatorial counting with repeated frequency values.
Clarify that every character in a k-subsequence must be unique.

Common Pitfalls or Variants

Common pitfalls

Assuming maximum beauty subsequences can include repeated characters.
Miscalculating combinations when multiple characters share the same frequency.
Sorting or selecting frequencies incorrectly leading to undercounting valid subsequences.

Follow-up variants

Find k-subsequences minimizing beauty instead of maximizing.
Allow subsequences with repeated characters and adjust counting.
Compute maximum beauty for subsequences of varying lengths simultaneously.

FAQ

What is a k-subsequence with maximum beauty?

It is a subsequence of length k with all unique characters that maximizes the sum of their frequencies in the string.

Can characters repeat in these subsequences?

No, each k-subsequence must contain unique characters; repetitions would reduce the count of valid maximum beauty subsequences.

Why use a greedy approach?

Selecting the k highest frequency characters ensures the sum of frequencies, or beauty, is maximized efficiently without checking all subsequences.

How do ties in frequencies affect counting?

Tied frequencies require combinatorial calculations to count all unique selections that achieve the same maximum beauty.

Is this problem related to hash tables and combinatorics?

Yes, hash tables track frequencies and combinatorial formulas count valid subsequences, directly reflecting the greedy choice plus invariant validation pattern.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        f = Counter(s)
        if len(f) < k:
            return 0
        mod = 10**9 + 7
        vs = sorted(f.values(), reverse=True)
        val = vs[k - 1]
        x = vs.count(val)
        ans = 1
        for v in vs:
            if v == val:
                break
            k -= 1
            ans = ans * v % mod
        ans = ans * comb(x, k) * pow(val, k, mod) % mod
        return ans

Continue Practicing

#2514 count anagrams #3518 smallest palindromic rearrangement ii #2844 minimum operations to make a special number