Algorithms
Hard
2842
3057
Count K-Subsequences of a String With Maximum Beauty
count-k-subsequences-of-a-string-with-maximum-beauty
"""
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:
   * "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') = 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 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.

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 * 105
 * 1 <= k <= s.length
 * s consists only of lowercase English letters.
"""
class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        
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:
   * "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') = 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 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.

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 * 105
 * 1 <= k <= s.length
 * s consists only of lowercase English letters.


Please complete the code below to solve above prblem:
```python
class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        
```

my_solution = Solution()

test_input = { "s": "bcca", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 4

test_input = { "s": "abbcd", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "am", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "az", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "ci", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "dd", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 0

test_input = { "s": "di", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "dw", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "ef", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "gq", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "hj", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "hx", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "ii", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 0

test_input = { "s": "il", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "jb", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "kx", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "qh", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "qk", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "qr", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "rg", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "rn", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "st", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "tb", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "tl", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "xc", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "auy", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "axm", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "dqc", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "fkp", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "fmk", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "fvl", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "hcx", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "iua", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "kzb", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "mhb", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "nzo", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "oof", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 0

test_input = { "s": "rfh", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "sty", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "sue", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "tba", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "tmc", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "wes", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "wvl", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "xho", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "xke", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "ysu", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "yxn", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "zco", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "zpq", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "axgn", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "dfyq", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 6

test_input = { "s": "dogq", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 6

test_input = { "s": "drbs", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 6

test_input = { "s": "elex", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 0

test_input = { "s": "fsaj", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 4

test_input = { "s": "fxau", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 6

test_input = { "s": "glbq", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "hzcj", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "minc", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 4

test_input = { "s": "nkim", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 4

test_input = { "s": "otpl", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 6

test_input = { "s": "pvrz", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "qwmy", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "rliu", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "tpig", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 6

test_input = { "s": "ucvh", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "vevt", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 4

test_input = { "s": "xstt", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "ypmv", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 4

test_input = { "s": "znoq", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 4

test_input = { "s": "bicnt", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 5

test_input = { "s": "bnhom", "k": 5 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "culhr", "k": 5 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 1

test_input = { "s": "dpfki", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 5

test_input = { "s": "dscbu", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 10

test_input = { "s": "edwlo", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 10

test_input = { "s": "ggsgo", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "guzzf", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "gzzzl", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 3

test_input = { "s": "kjojr", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 6

test_input = { "s": "kvsds", "k": 5 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 0

test_input = { "s": "ljdvp", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 5

test_input = { "s": "mdccc", "k": 5 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 0

test_input = { "s": "mmqny", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "mrbrj", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 6

test_input = { "s": "pwtbx", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 5

test_input = { "s": "qcxkr", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 10

test_input = { "s": "qvauy", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 5

test_input = { "s": "tzwoq", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 10

test_input = { "s": "ufxge", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 5

test_input = { "s": "unzxd", "k": 4 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 5

test_input = { "s": "vhqqj", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 6

test_input = { "s": "vnkbt", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 5

test_input = { "s": "wpbkz", "k": 2 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 10

test_input = { "s": "xdgvy", "k": 1 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 5

test_input = { "s": "yelem", "k": 5 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 0

test_input = { "s": "zwkhq", "k": 3 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 10

test_input = { "s": "anxnfi", "k": 5 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2

test_input = { "s": "cfbyuf", "k": 5 }
assert my_solution.countKSubsequencesWithMaxBeauty(**test_input) == 2