Count K-Subsequences of a String With Maximum Beauty

Count K-Subsequences of a String With Maximum Beauty - 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:
- "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 10^9 + 7.

Note: f(c) is the number of times a character c occurs in s, not a k-subsequence.

Input & Output

Example 1 — Basic Case

$ Input: s = "abbbdd", k = 2

› Output: 1

💡 Note: Characters: a(freq=1), b(freq=3), d(freq=2). For k=2, possible combinations are (a,b)→beauty=4, (a,d)→beauty=3, (b,d)→beauty=5. Maximum beauty is 5, achieved by 1 combination.

Example 2 — Multiple Ways

$ Input: s = "aabbcc", k = 2

› Output: 3

💡 Note: Each character appears twice. Any 2 characters give beauty=4. There are C(3,2)=3 ways to choose 2 from {a,b,c}.

Example 3 — Edge Case

$ Input: s = "abc", k = 1

› Output: 3

💡 Note: Each character appears once. Maximum beauty is 1, achieved by selecting any single character. 3 ways total.

Constraints

1 ≤ s.length ≤ 10⁴
1 ≤ k ≤ s.length
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String s with character frequencies and target subsequence length k

Beauty Calculation

Beauty = sum of f(c) for each character c in subsequence

Count Maximum

Count how many k-subsequences achieve the maximum possible beauty

Key Takeaway

🎯 Key Insight: Greedily select characters with highest frequencies and use combinatorics to count arrangements when frequencies are tied

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is that maximum beauty comes from selecting the k characters with highest frequencies. The optimal approach uses greedy selection combined with combinatorics to handle tied frequencies efficiently. Best approach: O(n + m log m) time, O(m) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All K-Subsequences	O(C(n,k) × n)	O(n)	Generate all possible k-subsequences with unique characters and find maximum beauty
Greedy with Combinatorics	O(n + m log m)	O(m)	Select k characters with highest frequencies and use combinatorics to count arrangements

Brute Force - Generate All K-Subsequences — Algorithm Steps

Count frequency of each character
Generate all combinations of k unique characters
Calculate beauty for each combination
Track maximum beauty and count of subsequences achieving it

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many times each character appears

Generate Combinations

Create all possible k-character combinations

Calculate Beauty

Sum frequencies for each combination and find maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_CHARS 26

int freq[MAX_CHARS];
char uniqueChars[MAX_CHARS];
int uniqueCount = 0;

void generateCombinations(int k, int start, int* current, int currentSize, int* maxBeauty, int* count) {
    if (currentSize == k) {
        int beauty = 0;
        for (int i = 0; i < k; i++) {
            beauty += freq[current[i]];
        }
        if (beauty > *maxBeauty) {
            *maxBeauty = beauty;
            *count = 1;
        } else if (beauty == *maxBeauty) {
            (*count)++;
        }
        return;
    }
    
    for (int i = start; i < uniqueCount; i++) {
        current[currentSize] = uniqueChars[i] - 'a';
        generateCombinations(k, i + 1, current, currentSize + 1, maxBeauty, count);
    }
}

int solution(char* s, int k) {
    memset(freq, 0, sizeof(freq));
    uniqueCount = 0;
    
    for (int i = 0; s[i]; i++) {
        freq[s[i] - 'a']++;
    }
    
    for (int i = 0; i < MAX_CHARS; i++) {
        if (freq[i] > 0) {
            uniqueChars[uniqueCount++] = 'a' + i;
        }
    }
    
    if (uniqueCount < k) return 0;
    
    int maxBeauty = 0;
    int count = 0;
    int current[MAX_CHARS];
    
    generateCombinations(k, 0, current, 0, &maxBeauty, &count);
    
    return count % MOD;
}

int main() {
    char s[1001];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    printf("%d\n", solution(s, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(n,k) × n)

C(n,k) combinations of k characters from n unique characters, each taking O(n) to process

✓ Linear Growth

Space Complexity

O(n)

Hash map to store character frequencies

⚡ Linearithmic Space

24.0K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All K-Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler