> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/heaps-and-priority-queue/2842.-count-k-subsequences-of-a-string-with-maximum-beauty.md).

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

## Problem Statement

<br>

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 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.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "bcca", k = 2
</strong><strong>Output: 4
</strong><strong>Explanation: From s we have f('a') = 1, f('b') = 1, and f('c') = 2.
</strong>The k-subsequences of s are: 
<strong>bcca having a beauty of f('b') + f('c') = 3 
</strong><strong>bcca having a beauty of f('b') + f('c') = 3 
</strong><strong>bcca having a beauty of f('b') + f('a') = 2 
</strong><strong>bcca having a beauty of f('c') + f('a') = 3
</strong><strong>bcca having a beauty of f('c') + f('a') = 3 
</strong>There are 4 k-subsequences that have the maximum beauty, 3. 
Hence, the answer is 4. 
</code></pre>

**Example 2:**

<pre><code><strong>Input: s = "abbcd", k = 4
</strong><strong>Output: 2
</strong><strong>Explanation: From s we have f('a') = 1, f('b') = 2, f('c') = 1, and f('d') = 1. 
</strong>The k-subsequences of s are: 
<strong>abbcd having a beauty of f('a') + f('b') + f('c') + f('d') = 5
</strong><strong>abbcd having a beauty of f('a') + f('b') + f('c') + f('d') = 5 
</strong>There are 2 k-subsequences that have the maximum beauty, 5. 
Hence, the answer is 2. 
</code></pre>

&#x20;

**Constraints:**

* `1 <= s.length <= 2 * 105`
* `1 <= k <= s.length`
* `s` consists only of lowercase English letters.

## Intuition

```
Approach:

MAintain the freq of elements
Take the elements greedily, By taking high freq element and so on

_ _ _ _ _

let say
a - 2
b - 2
c - 1
d - 1
e - 1

Now we take a,b compulsairly
 2 * 2 Combinations
Then for remaining 3 places , 3C3 combinations

```

### Links

<https://leetcode.com/problems/count-k-subsequences-of-a-string-with-maximum-beauty/>

### Video Links

<https://www.youtube.com/watch?v=74c6JV9DlHg&t=2s&ab_channel=AryanMittal>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
    int MOD = 1000000007;
    
    long long power(int x, int n) {
        if( n == 0) return 1;
        
        long long ans = power(x, n / 2);
        ans *= ans;
        ans %= MOD;
        
        if(n % 2 != 0) {
            ans *= x;
            ans %= MOD;
        }
        
        return ans;
    }
    
    long long fact(int n) {
        long long ans = 1;
        
        for(int i = 1; i <= n; i++) {
            ans *= i;
            ans %= MOD;
        }
        
        return ans;
    }
    
    long long nCr(int n, int r) {
        long long ans = fact(n);
        long long denominator = (fact(r) * fact(n - r)) % MOD;
        
        return (ans * power(denominator, MOD - 2)) % MOD;
    }
    
public:
    int countKSubsequencesWithMaxBeauty(string s, int k) {
        priority_queue<int> pq;
        
        vector<int> freq(26);
        for(auto x:s) {
            freq[x - 'a'] += 1;
        }
        
        for(int i = 0; i < 26; i++) {
            if(freq[i] > 0) pq.push(freq[i]);
        }
        
        if(pq.size() < k) {
            return 0;
        }
        
        long long ans = 1;
        while(k > 0) {
            int countEqual = 0, ele = pq.top();
            while(pq.size() > 0 && pq.top() == ele) {
                countEqual += 1;
                pq.pop();
            }
            
            if(countEqual <= k) {
                k -= countEqual;
                ans *= power(ele, countEqual);
                ans %= MOD;
            } else {
                ans *= power(ele, k);
                ans %= MOD;
                
                ans *= nCr(countEqual, k);
                ans %= MOD;
                break;
            }
        }
        
        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###