Scale Engineer

Count K-Subsequences of a String With Maximum Beauty

Hard
#2541Time: 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.
Patterns
MathGreedyCombinatorics
Data structures
Hash TableString

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem