#2842

Count K-Subsequences of a String With Maximum Beauty

international master · 1980 · lc hard +32 · verified · 30.2% accepted · 359 likes · top 7%

Description

A string s and an integer k are given. A k-subsequence is a length-k subsequence of s in which every character is unique.

Let f(c) be the frequency of character c in s.

The beauty of a k-subsequence is the sum of f(c) over all characters c in the subsequence.

For example, with s = "abbbdd" and k = 2:

- f('a') = 1, f('b') = 3, f('d') = 2

- The subsequence "bd" has beauty f('b') + f('d') = 5.

Return the number of k-subsequences with the maximum beauty, modulo 10⁹ + 7.

Notes

- f(c) counts occurrences in the full string, not in the subsequence.

- Two k-subsequences are distinct if they differ by at least one index.

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('a') = 2

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

There are 2 k-subsequences that have the maximum beauty, 5.

Hence, the answer is 2.

Code

1

2

3

class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:

class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int: