# 2842. Count K-Subsequences of a String With Maximum Beauty

## Description

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.

## Solutions

• class Solution {
public int countKSubsequencesWithMaxBeauty(String s, int k) {
int[] f = new int[26];
int n = s.length();
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (++f[s.charAt(i) - 'a'] == 1) {
++cnt;
}
}
if (cnt < k) {
return 0;
}
Integer[] vs = new Integer[cnt];
for (int i = 0, j = 0; i < 26; ++i) {
if (f[i] > 0) {
vs[j++] = f[i];
}
}
Arrays.sort(vs, (a, b) -> b - a);
final int mod = (int) 1e9 + 7;
long ans = 1;
int val = vs[k - 1];
int x = 0;
for (int v : vs) {
if (v == val) {
++x;
}
}
for (int v : vs) {
if (v == val) {
break;
}
--k;
ans = ans * v % mod;
}
int[][] c = new int[x + 1][x + 1];
for (int i = 0; i <= x; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i; ++j) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
ans = ((ans * c[x][k]) % mod) * qmi(val, k, mod) % mod;
return (int) ans;
}

long qmi(long a, long k, long p) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % p;
}
k >>= 1;
a = a * a % p;
}
return res;
}
}

• class Solution {
public:
int countKSubsequencesWithMaxBeauty(string s, int k) {
int f[26]{};
int cnt = 0;
for (char& c : s) {
if (++f[c - 'a'] == 1) {
++cnt;
}
}
if (cnt < k) {
return 0;
}
vector<int> vs(cnt);
for (int i = 0, j = 0; i < 26; ++i) {
if (f[i]) {
vs[j++] = f[i];
}
}
sort(vs.rbegin(), vs.rend());
const int mod = 1e9 + 7;
long long ans = 1;
int val = vs[k - 1];
int x = 0;
for (int v : vs) {
x += v == val;
}
for (int v : vs) {
if (v == val) {
break;
}
--k;
ans = ans * v % mod;
}
int c[x + 1][x + 1];
memset(c, 0, sizeof(c));
for (int i = 0; i <= x; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i; ++j) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
ans = (ans * c[x][k] % mod) * qmi(val, k, mod) % mod;
return ans;
}

long qmi(long a, long k, long p) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % p;
}
k >>= 1;
a = a * a % p;
}
return res;
}
};

• 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


• func countKSubsequencesWithMaxBeauty(s string, k int) int {
f := [26]int{}
cnt := 0
for _, c := range s {
f[c-'a']++
if f[c-'a'] == 1 {
cnt++
}
}
if cnt < k {
return 0
}
vs := []int{}
for _, x := range f {
if x > 0 {
vs = append(vs, x)
}
}
sort.Slice(vs, func(i, j int) bool {
return vs[i] > vs[j]
})
const mod int = 1e9 + 7
ans := 1
val := vs[k-1]
x := 0
for _, v := range vs {
if v == val {
x++
}
}
for _, v := range vs {
if v == val {
break
}
k--
ans = ans * v % mod
}
c := make([][]int, x+1)
for i := range c {
c[i] = make([]int, x+1)
c[i][0] = 1
for j := 1; j <= i; j++ {
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod
}
}
ans = (ans * c[x][k] % mod) * qmi(val, k, mod) % mod
return ans
}

func qmi(a, k, p int) int {
res := 1
for k != 0 {
if k&1 == 1 {
res = res * a % p
}
k >>= 1
a = a * a % p
}
return res
}

• function countKSubsequencesWithMaxBeauty(s: string, k: number): number {
const f: number[] = new Array(26).fill(0);
let cnt = 0;
for (const c of s) {
const i = c.charCodeAt(0) - 97;
if (++f[i] === 1) {
++cnt;
}
}
if (cnt < k) {
return 0;
}
const mod = 1e9 + 7;
const vs: number[] = f.filter(v => v > 0).sort((a, b) => b - a);
const val = vs[k - 1];
const x = vs.filter(v => v === val).length;
let ans = 1;
for (const v of vs) {
if (v === val) {
break;
}
--k;
ans = (ans * v) % mod;
}
const c: number[][] = new Array(x + 1).fill(0).map(() => new Array(k + 1).fill(0));
for (let i = 0; i <= x; ++i) {
c[i][0] = 1;
for (let j = 1; j <= Math.min(i, k); ++j) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
ans = (((ans * c[x][k]) % mod) * Number(qmi(BigInt(val), k, BigInt(mod)))) % mod;
return ans;
}

function qmi(a: bigint, k: number, p: bigint): bigint {
let res = 1n;
while (k) {
if ((k & 1) === 1) {
res = (res * a) % p;
}
k >>= 1;
a = (a * a) % p;
}
return res;
}