Count the number of good subsequences

Hash Table Math String Combinatorics Counting

48.3% acceptance

Mar 31, 2026

A subsequence of a string is good if it is not empty and the frequency of each one of its characters is the same. Given a string s, return the number of good subsequences of s. Since the answer may be too large, return it modulo 109 + 7. A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_good_subsequences(s: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut freq = [0usize; 26];
    for b in s.bytes() {
      freq[(b - b'a') as usize] += 1;
    }
    let max_freq = *freq.iter().max().unwrap();
    if max_freq == 0 {
      return 0;
    }

    // Precompute factorials and inverse factorials
    let n = s.len();
    let mut fact = vec![1i64; n + 1];
    for i in 1..=n {
      fact[i] = fact[i - 1] * i as i64 % MOD;
    }
    fn mod_pow(mut base: i64, mut exp: i64, m: i64) -> i64 {
      let mut r = 1i64;
      base %= m;
      while exp > 0 {
        if exp & 1 == 1 { r = r * base % m; }
        exp >>= 1;
        base = base * base % m;
      }
      r
    }
    let mut inv_fact = vec![1i64; n + 1];
    inv_fact[n] = mod_pow(fact[n], MOD - 2, MOD);
    for i in (0..n).rev() {
      inv_fact[i] = inv_fact[i + 1] * (i + 1) as i64 % MOD;
    }
    let comb = |n: usize, k: usize| -> i64 {
      if k > n { return 0; }
      fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD
    };

    let mut result = 0i64;
    for f in 1..=max_freq {
      let mut product = 1i64;
      for c in 0..26 {
        // For character c: either skip it (1 way) or choose f from freq[c]
        product = product * (1 + comb(freq[c], f)) % MOD;
      }
      // Subtract 1 for empty subsequence
      result = (result + product - 1 + MOD) % MOD;
    }
    result as i32
  }
}