Count the Number of Good Subsequences

Problem#

A good subsequence: every distinct character in it appears the same number of times. Count good subsequences of s (mod 10⁹ + 7).

Examples#

"aabb" → 11

Constraints#

1 <= s.length <= 10^4.

Approach#

Count frequencies. For each candidate per-character count k = 1..maxFreq, the number of subsequences where every present character appears exactly k times is Π (C(freq[c], k) + 1) - 1 (each char contributes “absent or k copies”, minus the all-absent option). Sum over k.

Solution#

class Solution {
public:
    int countGoodSubsequences(string s) {
        const int MOD = 1'000'000'007;
        int cnt[26] = {0};
        int maxFreq = 0;
        for (char c : s) maxFreq = max(maxFreq, ++cnt[c - 'a']);
        int n = s.size();
        vector<long long> fact(n + 1, 1), inv(n + 1, 1);
        auto pw = [&](long long b, long long e) {
            long long r = 1; b %= MOD;
            while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
            return r;
        };
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
        inv[n] = pw(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
        auto C = [&](int N, int K) -> long long {
            if (K < 0 || K > N) return 0;
            return fact[N] * inv[K] % MOD * inv[N - K] % MOD;
        };
        long long ans = 0;
        for (int k = 1; k <= maxFreq; ++k) {
            long long prod = 1;
            for (int c = 0; c < 26; ++c) {
                prod = prod * (1 + C(cnt[c], k)) % MOD;
            }
            ans = (ans + prod - 1 + MOD) % MOD;
        }
        return (int)ans;
    }
};

func countGoodSubsequences(s string) int {
    const MOD = 1_000_000_007
    var cnt [26]int
    maxFreq := 0
    for _, c := range s {
        cnt[c-'a']++
        if cnt[c-'a'] > maxFreq {
            maxFreq = cnt[c-'a']
        }
    }
    n := len(s)
    fact := make([]int64, n+1)
    inv := make([]int64, n+1)
    fact[0] = 1
    pw := func(b, e int64) int64 {
        r := int64(1)
        b %= MOD
        for e > 0 {
            if e&1 == 1 {
                r = r * b % MOD
            }
            b = b * b % MOD
            e >>= 1
        }
        return r
    }
    for i := 1; i <= n; i++ {
        fact[i] = fact[i-1] * int64(i) % MOD
    }
    inv[n] = pw(fact[n], MOD-2)
    for i := n - 1; i >= 0; i-- {
        inv[i] = inv[i+1] * int64(i+1) % MOD
    }
    C := func(N, K int) int64 {
        if K < 0 || K > N {
            return 0
        }
        return fact[N] * inv[K] % MOD * inv[N-K] % MOD
    }
    var ans int64
    for k := 1; k <= maxFreq; k++ {
        prod := int64(1)
        for c := 0; c < 26; c++ {
            prod = prod * (1 + C(cnt[c], k)) % MOD
        }
        ans = (ans + prod - 1 + MOD) % MOD
    }
    return int(ans)
}

from math import comb

class Solution:
    def countGoodSubsequences(self, s: str) -> int:
        MOD = 1_000_000_007
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - ord('a')] += 1
        max_freq = max(cnt)
        ans = 0
        for k in range(1, max_freq + 1):
            prod = 1
            for c in range(26):
                prod = prod * (1 + comb(cnt[c], k)) % MOD
            ans = (ans + prod - 1) % MOD
        return ans

function countGoodSubsequences(s) {
    const MOD = 1_000_000_007n;
    const cnt = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - 97]++;
    const maxFreq = Math.max(...cnt);
    const n = s.length;
    const power = (b, e) => {
        let r = 1n;
        b %= MOD;
        while (e > 0n) {
            if (e & 1n) r = (r * b) % MOD;
            b = (b * b) % MOD;
            e >>= 1n;
        }
        return r;
    };
    const fact = new Array(n + 1).fill(1n);
    for (let i = 1; i <= n; i++) fact[i] = (fact[i - 1] * BigInt(i)) % MOD;
    const inv = new Array(n + 1).fill(1n);
    inv[n] = power(fact[n], MOD - 2n);
    for (let i = n - 1; i >= 0; i--) inv[i] = (inv[i + 1] * BigInt(i + 1)) % MOD;
    const C = (N, K) => {
        if (K < 0 || K > N) return 0n;
        return (((fact[N] * inv[K]) % MOD) * inv[N - K]) % MOD;
    };
    let ans = 0n;
    for (let k = 1; k <= maxFreq; k++) {
        let prod = 1n;
        for (let c = 0; c < 26; c++) {
            prod = (prod * (1n + C(cnt[c], k))) % MOD;
        }
        ans = (ans + prod - 1n + MOD) % MOD;
    }
    return Number(ans);
}

class Solution {
    private static final int MOD = 1_000_000_007;
    private long[] fact;
    private long[] inv;

    public int countGoodSubsequences(String s) {
        int[] cnt = new int[26];
        int maxFreq = 0;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            cnt[idx]++;
            if (cnt[idx] > maxFreq) maxFreq = cnt[idx];
        }
        int n = s.length();
        fact = new long[n + 1];
        inv = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
        inv[n] = power(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
        long ans = 0;
        for (int k = 1; k <= maxFreq; k++) {
            long prod = 1;
            for (int c = 0; c < 26; c++) {
                prod = prod * (1 + comb(cnt[c], k)) % MOD;
            }
            ans = (ans + prod - 1 + MOD) % MOD;
        }
        return (int) ans;
    }

    private long comb(int N, int K) {
        if (K < 0 || K > N) return 0;
        return fact[N] * inv[K] % MOD * inv[N - K] % MOD;
    }

    private long power(long b, long e) {
        long r = 1;
        b %= MOD;
        while (e > 0) {
            if ((e & 1) == 1) r = r * b % MOD;
            b = b * b % MOD;
            e >>= 1;
        }
        return r;
    }
}

function countGoodSubsequences(s: string): number {
    const MOD = 1_000_000_007n;
    const cnt: number[] = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - 97]++;
    const maxFreq = Math.max(...cnt);
    const n = s.length;
    const power = (b: bigint, e: bigint): bigint => {
        let r = 1n;
        b %= MOD;
        while (e > 0n) {
            if (e & 1n) r = (r * b) % MOD;
            b = (b * b) % MOD;
            e >>= 1n;
        }
        return r;
    };
    const fact: bigint[] = new Array(n + 1).fill(1n);
    for (let i = 1; i <= n; i++) fact[i] = (fact[i - 1] * BigInt(i)) % MOD;
    const inv: bigint[] = new Array(n + 1).fill(1n);
    inv[n] = power(fact[n], MOD - 2n);
    for (let i = n - 1; i >= 0; i--) inv[i] = (inv[i + 1] * BigInt(i + 1)) % MOD;
    const C = (N: number, K: number): bigint => {
        if (K < 0 || K > N) return 0n;
        return (((fact[N] * inv[K]) % MOD) * inv[N - K]) % MOD;
    };
    let ans = 0n;
    for (let k = 1; k <= maxFreq; k++) {
        let prod = 1n;
        for (let c = 0; c < 26; c++) {
            prod = (prod * (1n + C(cnt[c], k))) % MOD;
        }
        ans = (ans + prod - 1n + MOD) % MOD;
    }
    return Number(ans);
}

Editorial#

For a fixed k, each letter independently contributes “0 copies” or “exactly k copies” — that’s 1 + C(freq[c], k) options. Multiplying across letters and subtracting the all-absent option yields good subsequences with target frequency k. Sum over all valid k.

Complexity#

Time: O(n + 26 * maxFreq).
Space: O(n).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#