Count k subsequences of a string with maximum beauty

Hash Table Math String Greedy Sorting Combinatorics

30.2% acceptance

Feb 25, 2026

359

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

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_k_subsequences_with_max_beauty(s: String, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let k = k as usize;
    let mut freq = [0i64; 26];
    for c in s.bytes() { freq[(c - b'a') as usize] += 1; }
    let mut freqs: Vec<i64> = freq.iter().filter(|&&f| f > 0).cloned().collect();
    if freqs.len() < k { return 0; }
    freqs.sort_unstable_by(|a, b| b.cmp(a));
    let threshold = freqs[k - 1];
    let above_count = freqs.iter().take_while(|&&f| f > threshold).count();
    let needed = k - above_count;
    let at_count = freqs.iter().filter(|&&f| f == threshold).count() as i64;

    fn pow_mod(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
      let mut r = 1i64; base %= modulus;
      while exp > 0 { if exp & 1 == 1 { r = r * base % modulus; } exp >>= 1; base = base * base % modulus; }
      r
    }
    fn comb(n: i64, r: i64, modulus: i64) -> i64 {
      if r > n || r < 0 { return 0; }
      let mut num = 1i64; let mut den = 1i64;
      for i in 0..r { num = num * ((n - i) % modulus) % modulus; den = den * ((i + 1) % modulus) % modulus; }
      num * pow_mod(den, modulus - 2, modulus) % modulus
    }

    let mut result = 1i64;
    for &f in freqs.iter().take(above_count) { result = result * (f % MOD) % MOD; }
    result = result * comb(at_count, needed as i64, MOD) % MOD;
    result = result * pow_mod(threshold, needed as i64, MOD) % MOD;
    result as i32
  }
}