# Count K-Subsequences of a String With Maximum Beauty
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-k-subsequences-of-a-string-with-maximum-beauty)
Canonical: https://scaleengineer.com/dsa/problems/count-k-subsequences-of-a-string-with-maximum-beauty
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Data structures:** Hash Table, String
---
## 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_ _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: 
**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:**

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

# Approaches
## Brute-Force Backtracking on Indices
This approach directly translates the problem definition into a solution. It involves generating all possible k-subsequences by picking `k` characters from the string `s` at different indices. For each valid k-subsequence (with unique characters), it calculates its beauty. The algorithm keeps track of the maximum beauty found so far and the count of subsequences achieving it.
**Time:** O(C(N, k) * k) - Where `N` is the length of `s`. `C(N, k)` is the number of ways to choose `k` indices from `N`. This is computationally infeasible for the given constraints. · **Space:** O(k) - The space is used for the recursion stack, which can go up to a depth of `k`, and to store the indices of the current subsequence.
**Pros:** Simple to understand as it directly models the problem statement.
**Cons:** Extremely inefficient due to the massive number of subsequences to check.; Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs.
### Explanation
The core of this method is a recursive helper function, say `backtrack(startIndex, currentSubsequenceIndices)`, which explores all possibilities of forming a k-subsequence by iterating through the string from `startIndex`.

In each recursive call, we add an index `i` to our `currentSubsequenceIndices` and recurse with `backtrack(i + 1, ...)`. The base case for the recursion is when the size of `currentSubsequenceIndices` becomes `k`. In the base case, we form the subsequence string and check if its characters are unique. If they are, we calculate its beauty by summing the pre-calculated frequencies of its characters.

We maintain global variables `maxBeauty` and `count`. If the current subsequence's beauty is greater than `maxBeauty`, we update `maxBeauty` and reset `count`. If it's equal, we increment `count`. This method is exhaustive and explores a very large search space, making it impractical for the given constraints.

```java
class Solution {
    long maxBeauty = -1;
    long count = 0;
    int k;
    String s;
    int[] freqs = new int[26];

    // This approach is too slow to be implemented fully due to TLE.
    // The following is a conceptual implementation.
    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        this.s = s;
        this.k = k;
        for (char c : s.toCharArray()) {
            freqs[c - 'a']++;
        }
        
        // The number of subsequences C(s.length(), k) is too large.
        // For example, C(2*10^5, 100) is astronomical.
        // A conceptual backtracking function would be called here:
        // backtrack(0, new ArrayList<>());
        
        // This approach is not feasible and is presented for theoretical understanding.
        return 0; // Placeholder for the result.
    }

    void backtrack(int start, java.util.List<Integer> indices) {
        if (indices.size() == k) {
            java.util.Set<Character> uniqueChars = new java.util.HashSet<>();
            long currentBeauty = 0;
            boolean isValid = true;
            for (int index : indices) {
                char c = s.charAt(index);
                if (!uniqueChars.add(c)) {
                    isValid = false;
                    break;
                }
            }

            if (isValid) {
                for (char c : uniqueChars) {
                    currentBeauty += freqs[c - 'a'];
                }

                if (currentBeauty > maxBeauty) {
                    maxBeauty = currentBeauty;
                    count = 1;
                } else if (currentBeauty == maxBeauty) {
                    count++;
                }
            }
            return;
        }

        if (start >= s.length()) {
            return;
        }

        for (int i = start; i < s.length(); i++) {
            indices.add(i);
            backtrack(i + 1, indices);
            indices.remove(indices.size() - 1); // backtrack
        }
    }
}
```
### Algorithm
1. Pre-calculate the frequency of each character in `s` and store it in a map or array.
2. Initialize `maxBeauty = -1` and `count = 0`.
3. Define a recursive function `backtrack(start, current_indices)`.
4. Base Case: If `current_indices.size() == k`:
    a. Construct the subsequence from `s` using `current_indices`.
    b. Check if all characters in the subsequence are unique.
    c. If unique, calculate its beauty using the pre-calculated frequencies.
    d. If beauty > `maxBeauty`, update `maxBeauty = beauty` and set `count = 1`.
    e. If beauty == `maxBeauty`, increment `count`.
    f. Return.
5. Recursive Step: For `i` from `start` to `s.length() - 1`:
    a. Add `i` to `current_indices`.
    b. Call `backtrack(i + 1, current_indices)`.
    c. Remove `i` from `current_indices` (backtrack).
6. Start the process by calling `backtrack(0, [])`.
7. Return `count`.

## Combinations of Unique Characters
A significant improvement over the brute-force approach is to realize that the beauty of a k-subsequence depends only on the set of `k` unique characters it contains, not their positions. The number of ways to form a subsequence with a given set of `k` characters is the product of their individual frequencies in the original string `s`. This approach first finds all unique characters in `s`, then generates all possible combinations of `k` characters from this set.
**Time:** O(N + C(A, k) * k) - `N` for frequency counting, `A` is alphabet size (26). The dominant part is generating `C(A, k)` combinations and processing each in `O(k)` time. · **Space:** O(A + k) which is O(k) - `A` is the alphabet size (26), so space is needed for frequencies and unique characters. The recursion depth is `k`.
**Pros:** Much more efficient than the first approach as it operates on the set of unique characters (at most 26) instead of string indices.; Correctly identifies the logic that beauty depends on the character set, not indices.
**Cons:** Can still be too slow if `k` is large (e.g., `k` is around 13), as `C(26, 13)` is a large number.; It recomputes the same beauty and count for different permutations of the same character set, though this is avoided by generating combinations.
### Explanation
First, we iterate through the string `s` to find all unique characters and their frequencies. Let the set of unique characters be `U`. If the number of unique characters is less than `k`, no k-subsequence with unique characters can be formed, so we return 0.

We then use a backtracking algorithm to generate all combinations of size `k` from the set `U`. For each combination of `k` characters, we calculate its total beauty by summing their frequencies. We also calculate the number of subsequences that can be formed with this character set, which is the product of their frequencies.

We maintain `maxBeauty` and `resultCount`. When we find a combination with beauty greater than `maxBeauty`, we update `maxBeauty` and set `resultCount` to the number of subsequences for this new combination. If we find a combination with beauty equal to `maxBeauty`, we add its subsequence count to `resultCount`. All calculations involving the count are done modulo `10^9 + 7`.

```java
class Solution {
    long maxBeauty = -1;
    long resultCount = 0;
    int k;
    int[] freqs = new int[26];
    java.util.List<Character> uniqueChars = new java.util.ArrayList<>();
    final int MOD = 1_000_000_007;

    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        this.k = k;
        for (char c : s.toCharArray()) {
            freqs[c - 'a']++;
        }

        for (int i = 0; i < 26; i++) {
            if (freqs[i] > 0) {
                uniqueChars.add((char) ('a' + i));
            }
        }

        if (uniqueChars.size() < k) {
            return 0;
        }

        generateCombinations(0, new java.util.ArrayList<>());
        return (int) resultCount;
    }

    void generateCombinations(int start, java.util.List<Character> currentCombination) {
        if (currentCombination.size() == k) {
            long currentBeauty = 0;
            long currentCount = 1;
            for (char c : currentCombination) {
                currentBeauty += freqs[c - 'a'];
                currentCount = (currentCount * freqs[c - 'a']) % MOD;
            }

            if (currentBeauty > maxBeauty) {
                maxBeauty = currentBeauty;
                resultCount = currentCount;
            } else if (currentBeauty == maxBeauty) {
                resultCount = (resultCount + currentCount) % MOD;
            }
            return;
        }

        if (start >= uniqueChars.size()) {
            return;
        }

        for (int i = start; i < uniqueChars.size(); i++) {
            currentCombination.add(uniqueChars.get(i));
            generateCombinations(i + 1, currentCombination);
            currentCombination.remove(currentCombination.size() - 1); // backtrack
        }
    }
}
```
### Algorithm
1. Calculate character frequencies for `s` and identify the set of unique characters `U`.
2. If `U.size() < k`, return 0.
3. Initialize `maxBeauty = -1` and `resultCount = 0`.
4. Use a recursive function `generateCombinations(start_index, current_combination)` to generate all `k`-sized combinations of characters from `U`.
5. Base Case: If `current_combination.size() == k`:
    a. Calculate the beauty of this combination by summing frequencies.
    b. Calculate the number of subsequences by multiplying frequencies (modulo `10^9 + 7`).
    c. If beauty > `maxBeauty`, update `maxBeauty` and set `resultCount` to the new subsequence count.
    d. If beauty == `maxBeauty`, add the new subsequence count to `resultCount` (modulo `10^9 + 7`).
    e. Return.
6. Recursive Step: For each character `c` from `start_index` in `U`:
    a. Add `c` to `current_combination`.
    b. Call `generateCombinations(i + 1, current_combination)`.
    c. Remove `c` (backtrack).
7. Start by calling `generateCombinations(0, [])`.
8. Return `resultCount`.

## Greedy Selection with Combinatorics
The most efficient approach leverages a key insight: to maximize beauty, we must greedily choose the `k` unique characters with the highest frequencies. The problem then reduces to counting how many ways we can form k-subsequences using these top `k` frequency characters, correctly handling ties using combinatorics.
**Time:** O(N + A log A) - `N` for frequency counting, `A` for alphabet size. Sorting the unique frequencies takes `A log A`. Since `A` is a constant (26), the complexity simplifies to O(N). · **Space:** O(A) or O(1) - Where `A` is the alphabet size (26). Space is used for the frequency array, the frequency-to-count map, and precomputed factorials.
**Pros:** Highly efficient and optimal.; Correctly handles ties in frequencies using combinatorics.; Scales well with the input size `N`.
**Cons:** Requires understanding of modular arithmetic, including modular exponentiation and combinations, which adds implementation complexity.
### Explanation
The core idea is that the maximum beauty is achieved by summing the `k` largest character frequencies. We don't need to find the maximum beauty first; we can directly calculate the count of subsequences that will have this maximum beauty.

1.  First, we compute the frequency of each of the 26 lowercase letters in `s`.
2.  We then group these characters by their frequency. A map `freqToCount` can store this: `frequency -> number of characters with this frequency`.
3.  We iterate through the frequencies in descending order. For each frequency level `f` with `c` characters:
    *   If we can take all `c` characters without exceeding our target `k` (i.e., `c <= k`), we must include them all to maximize beauty. The number of ways to form subsequences from them is `f^c`. We multiply our running answer by this value and decrease `k` by `c`.
    *   If we cannot take all `c` characters (i.e., `c > k`), it means this is the last frequency level we'll consider. We need to choose the remaining `k` characters from the `c` available. The number of ways to choose the characters is `C(c, k)`. For each of these `k` chosen characters, we can pick any of their `f` occurrences. So we multiply the answer by `C(c, k) * (f^k)`. After this, we have selected all `k` characters, so we can stop.

This requires helper functions for modular exponentiation (`power`) and combinations (`nCr`), both operating under the modulo `10^9 + 7`.

```java
class Solution {
    final int MOD = 1_000_000_007;
    long[] fact;
    long[] invFact;

    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        int[] freqs = new int[26];
        int uniqueCharCount = 0;
        for (char c : s.toCharArray()) {
            if (freqs[c - 'a'] == 0) {
                uniqueCharCount++;
            }
            freqs[c - 'a']++;
        }

        if (uniqueCharCount < k) {
            return 0;
        }

        precomputeFactorials(27);

        java.util.Map<Integer, Integer> freqToCount = new java.util.HashMap<>();
        for (int freq : freqs) {
            if (freq > 0) {
                freqToCount.put(freq, freqToCount.getOrDefault(freq, 0) + 1);
            }
        }

        java.util.List<Integer> sortedFreqKeys = new java.util.ArrayList<>(freqToCount.keySet());
        java.util.Collections.sort(sortedFreqKeys, java.util.Collections.reverseOrder());

        long ans = 1;
        int remainingK = k;

        for (int freq : sortedFreqKeys) {
            int count = freqToCount.get(freq);
            if (count <= remainingK) {
                ans = (ans * power(freq, count)) % MOD;
                remainingK -= count;
            } else { // count > remainingK
                long waysToChoose = combinations(count, remainingK);
                long waysToFormSubsequences = power(freq, remainingK);
                ans = (ans * waysToChoose) % MOD;
                ans = (ans * waysToFormSubsequences) % MOD;
                remainingK = 0;
            }
            if (remainingK == 0) {
                break;
            }
        }

        return (int) ans;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    private long modInverse(long n) {
        return power(n, MOD - 2);
    }

    private void precomputeFactorials(int n) {
        fact = new long[n];
        invFact = new long[n];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i < n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = modInverse(fact[i]);
        }
    }

    private long combinations(int n, int k) {
        if (k < 0 || k > n) return 0;
        return (((fact[n] * invFact[k]) % MOD) * invFact[n - k]) % MOD;
    }
}
```
### Algorithm
1. Count frequencies of all 26 characters in `s`.
2. Create a map `freqToCount` where `freqToCount[f]` is the number of characters with frequency `f`.
3. If the total number of unique characters is less than `k`, return 0.
4. Get a sorted list of unique frequencies in descending order.
5. Initialize `ans = 1` and `remainingK = k`.
6. Iterate through the sorted frequencies `f`:
    a. Let `count = freqToCount[f]`.
    b. If `count <= remainingK`:
        i. We take all `count` characters. Multiply `ans` by `power(f, count)`.
        ii. Decrement `remainingK` by `count`.
    c. Else (`count > remainingK`):
        i. We need to choose `remainingK` characters from `count`.
        ii. Multiply `ans` by `combinations(count, remainingK)`.
        iii. Multiply `ans` by `power(f, remainingK)`.
        iv. Set `remainingK = 0` and break the loop.
7. Return `ans`.

# Solutions
### Java

```java
class Solution {
private
  final int mod = (int)1 e9 + 7;
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);
    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) * qpow(val, k) % mod;
    return (int)ans;
  }
private
  long qpow(long a, int n) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return ans;
  }
}

```

### CPP

```cpp
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;
      }
    }
    auto qpow = [&](long long a, int n) {
      long long ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
      }
      return ans;
    };
    ans = (ans * c[x][k] % mod) * qpow(val, k) % mod;
    return ans;
  }
};

```

### Python

```python
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

```