Count K-Subsequences of a String With Maximum Beauty

Problem

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 s are:
- "_**ab**_ bbdd" -> "ab" having a beauty of f('a') + f('b') = 4
- "_**a**_ bbb** _d_** d" -> "ad" having a beauty of f('a') + f('d') = 3
- "a** _b_** bb _**d**_ d" -> "bd" having a beauty of f('b') + f('d') = 5

Return an integer denoting the number of k-subsequences whosebeauty is the maximum among all k-subsequences. Since the answer may be too large, return it modulo 10^9 + 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.
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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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: 
**_bc_** ca having a beauty of f('b') + f('c') = 3 
**_b_** c _**c**_ a having a beauty of f('b') + f('c') = 3 
**_b_** cc** _a_** having a beauty of f('b') + f('a') = 2 
b** _c_** c _**a**_**** having a beauty of f('c') + f('a') = 3
bc** _ca_** 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

1
2
3
4
5
6
7
8


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: 
_**ab**_ b** _cd_** having a beauty of f('a') + f('b') + f('c') + f('d') = 5
_**a**_ b _**bcd**_ 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 * 10^5
1 <= k <= s.length
s consists only of lowercase English letters.

Solution

Method 1 – Greedy + Combinatorics

Intuition

To maximize the beauty of a k-subsequence, we should pick the k most frequent unique characters. The more frequent a character, the more ways it can be chosen in a subsequence, and the higher the beauty sum. The number of such subsequences is determined by the product of the frequencies (as each character can be picked from its occurrences in the string).

Approach

Count the frequency of each character in the string.
If there are fewer than k unique characters, return 0 (not possible).
Sort the frequencies in descending order.
Select the top k frequencies. The sum of these is the maximum beauty.
For each character with the k-th highest frequency, count how many such characters there are (could be ties).
Use combinatorics to count the number of ways to pick k characters from the available unique characters with the top k frequencies.
For each selection, multiply the number of ways to pick each character from its occurrences.
Return the result modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
public:
    int countKSubsequencesWithMaxBeauty(string s, int k) {
        const int MOD = 1e9+7;
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        vector<int> f;
        for (auto& p : freq) f.push_back(p.second);
        if ((int)f.size() < k) return 0;
        sort(f.rbegin(), f.rend());
        int kth = f[k-1], cnt = 0, total = 0;
        for (int x : f) if (x == kth) cnt++;
        for (int i = 0; i < k; ++i) if (f[i] == kth) total++;
        long long ans = 1;
        for (int i = 0; i < k; ++i) ans = ans * f[i] % MOD;
        // C(cnt, total)
        for (int i = 1; i <= total; ++i) ans = ans * (cnt - i + 1) % MOD;
        for (int i = 1; i <= total; ++i) ans = ans * powmod(i, MOD-2, MOD) % MOD;
        return (int)ans;
    }
    long long powmod(long long a, long long b, long long m) {
        long long r = 1;
        while (b) {
            if (b & 1) r = r * a % m;
            a = a * a % m;
            b >>= 1;
        }
        return r;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


func powmod(a, b, m int) int {
    res := 1
    a = a % m
    for b > 0 {
        if b&1 == 1 {
            res = res * a % m
        }
        a = a * a % m
        b >>= 1
    }
    return res
}

func countKSubsequencesWithMaxBeauty(s string, k int) int {
    const MOD = 1e9 + 7
    freq := make(map[rune]int)
    for _, c := range s {
        freq[c]++
    }
    f := []int{}
    for _, v := range freq {
        f = append(f, v)
    }
    if len(f) < k {
        return 0
    }
    sort.Slice(f, func(i, j int) bool { return f[i] > f[j] })
    kth, cnt, total := f[k-1], 0, 0
    for _, x := range f {
        if x == kth {
            cnt++
        }
    }
    for i := 0; i < k; i++ {
        if f[i] == kth {
            total++
        }
    }
    ans := 1
    for i := 0; i < k; i++ {
        ans = ans * f[i] % MOD
    }
    for i := 1; i <= total; i++ {
        ans = ans * (cnt-i+1) % MOD
    }
    for i := 1; i <= total; i++ {
        ans = ans * powmod(i, MOD-2, MOD) % MOD
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    static final int MOD = 1000000007;
    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) freq.put(c, freq.getOrDefault(c, 0) + 1);
        List<Integer> f = new ArrayList<>(freq.values());
        if (f.size() < k) return 0;
        f.sort(Collections.reverseOrder());
        int kth = f.get(k-1), cnt = 0, total = 0;
        for (int x : f) if (x == kth) cnt++;
        for (int i = 0; i < k; ++i) if (f.get(i) == kth) total++;
        long ans = 1;
        for (int i = 0; i < k; ++i) ans = ans * f.get(i) % MOD;
        for (int i = 1; i <= total; ++i) ans = ans * (cnt - i + 1) % MOD;
        for (int i = 1; i <= total; ++i) ans = ans * powmod(i, MOD-2, MOD) % MOD;
        return (int)ans;
    }
    long powmod(long a, long b, long m) {
        long r = 1;
        while (b > 0) {
            if ((b & 1) == 1) r = r * a % m;
            a = a * a % m;
            b >>= 1;
        }
        return r;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    private val MOD = 1_000_000_007L
    fun countKSubsequencesWithMaxBeauty(s: String, k: Int): Int {
        val freq = s.groupingBy { it }.eachCount().values.toList()
        if (freq.size < k) return 0
        val f = freq.sortedDescending()
        val kth = f[k-1]
        val cnt = f.count { it == kth }
        val total = f.take(k).count { it == kth }
        var ans = 1L
        for (i in 0 until k) ans = ans * f[i] % MOD
        for (i in 1..total) ans = ans * (cnt-i+1) % MOD
        for (i in 1..total) ans = ans * powmod(i.toLong(), MOD-2, MOD) % MOD
        return ans.toInt()
    }
    private fun powmod(a: Long, b: Long, m: Long): Long {
        var res = 1L; var aa = a; var bb = b
        while (bb > 0) {
            if (bb and 1L == 1L) res = res * aa % m
            aa = aa * aa % m
            bb = bb shr 1
        }
        return res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        MOD = 10**9 + 7
        from collections import Counter
        freq = Counter(s)
        f = list(freq.values())
        if len(f) < k:
            return 0
        f.sort(reverse=True)
        kth = f[k-1]
        cnt = sum(1 for x in f if x == kth)
        total = sum(1 for x in f[:k] if x == kth)
        ans = 1
        for i in range(k):
            ans = ans * f[i] % MOD
        from math import comb
        ans = ans * comb(cnt, total) % MOD
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


impl Solution {
    pub fn count_k_subsequences_with_max_beauty(s: String, k: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        for c in s.chars() {
            *freq.entry(c).or_insert(0) += 1;
        }
        let mut f: Vec<i64> = freq.values().cloned().collect();
        if f.len() < k as usize {
            return 0;
        }
        f.sort_unstable_by(|a, b| b.cmp(a));
        let kth = f[(k-1) as usize];
        let cnt = f.iter().filter(|&&x| x == kth).count() as i64;
        let total = f.iter().take(k as usize).filter(|&&x| x == kth).count() as i64;
        let mut ans = 1i64;
        for i in 0..k as usize {
            ans = ans * f[i] % MOD;
        }
        ans = ans * comb(cnt, total, MOD) % MOD;
        ans as i32
    }
}
fn comb(n: i64, k: i64, m: i64) -> i64 {
    let mut num = 1i64;
    let mut den = 1i64;
    for i in 0..k {
        num = num * (n - i) % m;
        den = den * (i + 1) % m;
    }
    num * powmod(den, m-2, m) % m
}
fn powmod(mut a: i64, mut b: i64, m: i64) -> i64 {
    let mut r = 1i64;
    while b > 0 {
        if b & 1 == 1 {
            r = r * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    r
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
    countKSubsequencesWithMaxBeauty(s: string, k: number): number {
        const MOD = 1e9 + 7;
        const freq: Record<string, number> = {};
        for (const c of s) freq[c] = (freq[c] || 0) + 1;
        const f = Object.values(freq);
        if (f.length < k) return 0;
        f.sort((a, b) => b - a);
        const kth = f[k-1];
        let cnt = 0, total = 0;
        for (const x of f) if (x === kth) cnt++;
        for (let i = 0; i < k; ++i) if (f[i] === kth) total++;
        let ans = 1;
        for (let i = 0; i < k; ++i) ans = ans * f[i] % MOD;
        ans = ans * comb(cnt, total, MOD) % MOD;
        return ans;
    }
}
function comb(n: number, k: number, m: number): number {
    let num = 1, den = 1;
    for (let i = 0; i < k; ++i) {
        num = num * (n - i) % m;
        den = den * (i + 1) % m;
    }
    return num * powmod(den, m-2, m) % m;
}
function powmod(a: number, b: number, m: number): number {
    let r = 1;
    while (b > 0) {
        if (b & 1) r = r * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return r;
}

Complexity

⏰ Time complexity: O(n + u log u) where n is the length of s and u is the number of unique characters. Counting frequencies is O(n), sorting is O(u log u), and the rest is O(u).
🧺 Space complexity: O(u) for storing character frequencies and sorted list.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Greedy + Combinatorics#

Intuition#

Approach#

Code#

Complexity#