3057. Count K-Subsequences of a String With Maximum Beauty
My accepted C++ solution to LeetCode problem 3057, Count K-Subsequences of a String With Maximum Beauty, running in 2ms.
- Difficulty: Hard
- C++
- Runtime 2ms
- Memory 17MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
C++
Accepted on LeetCode — runtime 2ms, memory 17MB, accepted 2025-12-27.
class Solution {
public:
const int MOD = 1e9 + 7;
long long power(long long base, long long exp, long long mod) {
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) result = result * base % mod;
base = base * base % mod;
exp /= 2;
}
return result;
}
int countKSubsequencesWithMaxBeauty(string s, int k) {
vector<int> freq(26, 0);
for (char c : s) freq[c - 'a']++;
vector<int> counts;
for (int f : freq) if (f > 0) counts.push_back(f);
if (k > counts.size()) return 0;
sort(counts.rbegin(), counts.rend());
int threshold = counts[k - 1];
int cntThreshold = 0, cntAbove = 0;
for (int c : counts) {
if (c > threshold) cntAbove++;
else if (c == threshold) cntThreshold++;
}
int need = k - cntAbove;
long long result = 1;
for (int i = 0; i < cntAbove; i++) result = result * counts[i] % MOD;
result = result * power(threshold, need, MOD) % MOD;
long long comb = 1;
for (int i = 0; i < need; i++) {
comb = comb * (cntThreshold - i) % MOD;
comb = comb * power(i + 1, MOD - 2, MOD) % MOD;
}
return result * comb % MOD;
}
};