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

Last updated: March 5, 2025

In this guide, you will get 2842. Count K-Subsequences of a String With Maximum Beauty LeetCode Solution with the best time and space complexity. The solution to Count K-Subsequences of a String With Maximum Beauty problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count K-Subsequences of a String With Maximum Beauty solution in C++
Count K-Subsequences of a String With Maximum Beauty solution in Java
Count K-Subsequences of a String With Maximum Beauty solution in Python
Additional Resources

2842. Count K-Subsequences of a String With Maximum Beauty LeetCode Solution image

Problem Statement of 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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2842. Count K-Subsequences of a String With Maximum Beauty LeetCode Solution in C++

class Solution {
 public:
  int countKSubsequencesWithMaxBeauty(string s, int k) {
    unordered_map<char, int> count;
    for (const char c : s)
      ++count[c];
    if (count.size() < k)
      return 0;

    long ans = 1;

    for (const auto& [fc, numOfChars] : getFreqCountPairs(count)) {
      if (numOfChars >= k) {
        ans *= nCk(numOfChars, k);
        ans %= kMod;
        return ans * modPow(fc, k) % kMod;
      }
      ans *= modPow(fc, numOfChars);
      ans %= kMod;
      k -= numOfChars;
    }

    return ans;
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  vector<pair<int, int>> getFreqCountPairs(
      const unordered_map<char, int>& count) {
    unordered_map<int, int> freqCount;
    for (const auto& [_, value] : count)
      ++freqCount[value];
    vector<pair<int, int>> freqCountPairs;
    for (const auto& [fc, numOfChars] : freqCount)
      freqCountPairs.emplace_back(fc, numOfChars);
    ranges::sort(freqCountPairs, ranges::greater{},
                 [](const pair<int, int>& freqCountPair) {
      return freqCountPair.first;
    });
    return freqCountPairs;
  }

  long nCk(int n, int k) {
    long res = 1;
    for (int i = 1; i <= k; ++i)
      res = res * (n - i + 1) / i;
    return res;
  }

  long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % kMod, (n - 1)) % kMod;
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
};
/* code provided by PROGIEZ */

2842. Count K-Subsequences of a String With Maximum Beauty LeetCode Solution in Java

class Solution {
  public int countKSubsequencesWithMaxBeauty(String s, int k) {
    Map<Character, Integer> count = new HashMap<>();
    for (final char c : s.toCharArray())
      count.merge(c, 1, Integer::sum);
    if (count.size() < k)
      return 0;

    long ans = 1;

    for (Pair<Integer, Integer> pair : getFreqCountPairs(count)) {
      final int fc = pair.getKey();
      final int numOfChars = pair.getValue();
      if (numOfChars >= k) {
        ans *= nCk(numOfChars, k) * modPow(fc, k);
        return (int) (ans % kMod);
      }
      ans *= modPow(fc, numOfChars);
      ans %= kMod;
      k -= numOfChars;
    }

    return (int) ans;
  }

  private static final int kMod = 1_000_000_007;

  private List<Pair<Integer, Integer>> getFreqCountPairs(Map<Character, Integer> count) {
    // freqCount := (f(c), # of chars with f(c))
    Map<Integer, Integer> freqCount = new HashMap<>();
    for (final int value : count.values())
      freqCount.merge(value, 1, Integer::sum);
    List<Pair<Integer, Integer>> freqCountPairs = new ArrayList<>();
    for (Map.Entry<Integer, Integer> entry : freqCount.entrySet())
      freqCountPairs.add(new Pair<>(entry.getKey(), entry.getValue()));
    freqCountPairs.sort((a, b) -> b.getKey().compareTo(a.getKey()));
    return freqCountPairs;
  }

  private long nCk(int n, int k) {
    long res = 1;
    for (int i = 1; i <= k; ++i)
      res = res * (n - i + 1) / i;
    return res;
  }

  private int modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return (int) (x * modPow(x % kMod, (n - 1)) % kMod);
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
}
// code provided by PROGIEZ

2842. Count K-Subsequences of a String With Maximum Beauty LeetCode Solution in Python

class Solution:
  def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
    kMod = 1_000_000_007
    count = collections.Counter(s)
    if len(count) < k:
      return 0

    ans = 1
    # freqCount := (f(c), # of chars with f(c))
    freqCount = collections.Counter(count.values())

    for fc, numOfChars in list(sorted(freqCount.items(), reverse=True)):
      if numOfChars >= k:
        ans *= math.comb(numOfChars, k) * pow(fc, k, kMod)
        return ans % kMod
      ans *= pow(fc, numOfChars, kMod)
      ans %= kMod
      k -= numOfChars
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents