Count K-Subsequences of a String With Maximum Beauty solution and explanation

from collections import Counter
from math import comb

MOD = 10**9 + 7
def count_max_beauty_k_subsequences(s, k):
    char_count = Counter(s)
    char_freq = sorted(char_count.values(), reverse=True)
    max_beauty = sum(char_freq[:k])
    num_max_beauty_subseq = 1
    available_positions = [freq for freq in char_freq if freq in char_freq[:k]]
    for freq in available_positions:
        num_max_beauty_subseq *= comb(freq, available_positions.count(freq))
        num_max_beauty_subseq %= MOD
    return num_max_beauty_subseq

s = "bcca"
k = 2
print(count_max_beauty_k_subsequences(s, k)) # Output: 4

import java.util.*;

public class MaxBeautyKSubsequence {
    public static final int MOD = 1000000007;
    
    public static int countMaxBeautyKSubsequences(String s, int k) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        List<Integer> freqList = new ArrayList<>(freqMap.values());
        Collections.sort(freqList, Collections.reverseOrder());

        int maxBeauty = 0;
        for (int i = 0; i < k; i++) {
            maxBeauty += freqList.get(i);
        }

        long numMaxBeautySubseq = 1;
        for (int i = 0; i < k; i++) {
            numMaxBeautySubseq = (numMaxBeautySubseq * combinations(freqList.get(i), 1)) % MOD;
        }

        return (int) numMaxBeautySubseq;
    }
    
    private static long combinations(int n, int r) {
        if (r > n) return 0;
        r = Math.min(r, n - r);
        long res = 1;
        for (int i = 1; i <= r; i++) {
            res = res * (n - i + 1) / i;
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "bcca";
        int k = 2;
        System.out.println(countMaxBeautyKSubsequences(s, k)); // Output: 4
    }
}

MOD = 10**9 + 7
from collections import Counter

class Solution:
    def maxBeautyKSubsequence(self, s: str, k: int) -> int:
        char_count = Counter(s)
        freq_sorted = sorted(char_count.values(), reverse=True)

        if len(freq_sorted) < k:
            return 0

        max_beauty = sum(freq_sorted[:k])
        subseq_count = 1
        for i in range(k):
            subseq_count *= freq_sorted[i]
            subseq_count %= MOD
        return subseq_count

sol = Solution()
print(sol.maxBeautyKSubsequence('bcca', 2)) # Output: 4

import java.util.*;

public class Solution {
    final static int MOD = 1000000007;

    public int maxBeautyKSubsequence(String s, int k) {
        HashMap<Character, Integer> charCount = new HashMap<>();

        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        List<Integer> frequencies = new ArrayList<>(charCount.values());
        frequencies.sort(Collections.reverseOrder());

        if (frequencies.size() < k) return 0;

        int maxBeauty = 0;
        long subseqCount = 1;
        for (int i = 0; i < k; i++) {
            maxBeauty += frequencies.get(i);
            subseqCount = (subseqCount * frequencies.get(i)) % MOD;
        }

        return (int) subseqCount;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxBeautyKSubsequence("bcca", 2)); // Output: 4
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define MOD 1000000007

using namespace std;

class Solution {
public:
    int maxBeautyKSubsequence(string s, int k) {
        unordered_map<char, int> charCount;

        for (auto c : s) {
            charCount[c]++;
        }

        vector<int> frequencies;
        for (auto& p : charCount) {
            frequencies.push_back(p.second);
        }
        sort(frequencies.rbegin(), frequencies.rend());

        if (frequencies.size() < k) return 0;

        int maxBeauty = 0;
        long long subseqCount = 1;
        for (int i = 0; i < k; i++) {
            maxBeauty += frequencies[i];
            subseqCount = (subseqCount * frequencies[i]) % MOD;
        }

        return (int)subseqCount;
    }
};

int main() {
    Solution sol;
    cout << sol.maxBeautyKSubsequence("bcca", 2) << endl; // Output: 4
    return 0;
}

const MOD = 1e9 + 7;

function maxBeautyKSubsequence(s, k) {
    const charCount = {};
    for (const char of s) {
        charCount[char] = (charCount[char] || 0) + 1;
    }

    const frequencies = Object.values(charCount).sort((a, b) => b - a);
    if (frequencies.length < k) return 0;

    let maxBeauty = 0, subseqCount = 1;
    for (let i = 0; i < k; i++) {
        maxBeauty += frequencies[i];
        subseqCount = (subseqCount * frequencies[i]) % MOD;
    }

    return subseqCount;
}

console.log(maxBeautyKSubsequence("bcca", 2)); // Output: 4

function countKSubsequencesWithMaxBeauty(s: string, k: number): number {
    const f: number[] = new Array(26).fill(0);
    let cnt = 0;
    for (const c of s) {
        const i = c.charCodeAt(0) - 97;
        if (++f[i] === 1) {
            ++cnt;
        }
    }
    if (cnt < k) {
        return 0;
    }
    const mod = BigInt(10 ** 9 + 7);
    const vs: number[] = f.filter(v => v > 0).sort((a, b) => b - a);
    const val = vs[k - 1];
    const x = vs.filter(v => v === val).length;
    let ans = 1n;
    for (const v of vs) {
        if (v === val) {
            break;
        }
        --k;
        ans = (ans * BigInt(v)) % mod;
    }
    const c: number[][] = new Array(x + 1).fill(0).map(() => new Array(k + 1).fill(0));
    for (let i = 0; i <= x; ++i) {
        c[i][0] = 1;
        for (let j = 1; j <= Math.min(i, k); ++j) {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % Number(mod);
        }
    }
    const qpow = (a: bigint, n: number): bigint => {
        let ans = 1n;
        for (; n; n >>>= 1) {
            if (n & 1) {
                ans = (ans * a) % BigInt(mod);
            }
            a = (a * a) % BigInt(mod);
        }
        return ans;
    };
    ans = (((ans * BigInt(c[x][k])) % mod) * qpow(BigInt(val), k)) % mod;
    return Number(ans);
}

func countKSubsequencesWithMaxBeauty(s string, k int) int {
	f := [26]int{}
	cnt := 0
	for _, c := range s {
		f[c-'a']++
		if f[c-'a'] == 1 {
			cnt++
		}
	}
	if cnt < k {
		return 0
	}
	vs := []int{}
	for _, x := range f {
		if x > 0 {
			vs = append(vs, x)
		}
	}
	sort.Slice(vs, func(i, j int) bool {
		return vs[i] > vs[j]
	})
	const mod int = 1e9 + 7
	ans := 1
	val := vs[k-1]
	x := 0
	for _, v := range vs {
		if v == val {
			x++
		}
	}
	for _, v := range vs {
		if v == val {
			break
		}
		k--
		ans = ans * v % mod
	}
	c := make([][]int, x+1)
	for i := range c {
		c[i] = make([]int, x+1)
		c[i][0] = 1
		for j := 1; j <= i; j++ {
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod
		}
	}
	qpow := func(a, n int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	ans = (ans * c[x][k] % mod) * qpow(val, k) % mod
	return ans
}