# 2539. Count the Number of Good Subsequences

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 class Solution { public: int countGoodSubsequences(string s) { // For each frequency f in [1, max(freq)], start with "" and calculate how // many subseqs can be constructed with each letter's frequency = f. // // E.g., s = "abb", so f = max(freq) = 2. // // For f = 1, with 1 way to build "", choose any 'a' to construct a good // subseq, so # of good subseqs = 1 + 1 * (1, 1) = 2 ("", "a"). Next, add // 'b' and # of good subseqs = 2 + 2 * (2, 1) = 6 ("", "a", "b1", "b2", // "ab1", "ab2"). So, the # of good subseqs for f = 1 is 5 since we need to // exclude "". // // For f = 2, with 1 way to build "", choose any two 'b's to construct a // good subseq, so # of good subseqs = 1 + 1 * (2, 2) is 2 ("", "bb"). So, // the # of good subseqs for f = 2 = 1 since we need to exclude "". // // Therefore, the # of good subseqs for "aab" = 5 + 1 = 6. constexpr int kMod = 1'000'000'007; int ans = 0; vector count(26); for (const char c : s) ++count[c - 'a']; const int maxFreq = *max_element(begin(count), end(count)); const auto [fact, invFact] = getFactAndInvFact(maxFreq, kMod); for (int freq = 1; freq <= maxFreq; ++freq) { long numSubseqs = 1; // "" for (const int charFreq : count) if (charFreq >= freq) numSubseqs = (numSubseqs + numSubseqs * nCk(charFreq, freq, fact, invFact, kMod)) % kMod; ans += numSubseqs - 1; // Minus "" ans %= kMod; } return ans; } private: int nCk(int n, int k, const vector& fact, const vector& invFact, int kMod) { return fact[n] * invFact[k] % kMod * invFact[n - k] % kMod; } pair, vector> getFactAndInvFact(int n, int kMod) { vector fact(n + 1); vector invFact(n + 1); vector inv(n + 1); fact[0] = invFact[0] = 1; inv[0] = inv[1] = 1; for (int i = 1; i <= n; ++i) { if (i >= 2) inv[i] = kMod - kMod / i * inv[kMod % i] % kMod; fact[i] = fact[i - 1] * i % kMod; invFact[i] = invFact[i - 1] * inv[i] % kMod; } return {fact, invFact}; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 class Solution { public int countGoodSubsequences(String s) { // For each frequency f in [1, max(freq)], start with "" and calculate how // many subseqs can be finalructed with each letter's frequency = f. // // E.g., s = "abb", so f = max(freq) = 2. // // For f = 1, with 1 way to build "", choose any 'a' to finalruct a good // subseq, so # of good subseqs = 1 + 1 * (1, 1) = 2 ("", "a"). Next, add // 'b' and # of good subseqs = 2 + 2 * (2, 1) = 6 ("", "a", "b1", "b2", // "ab1", "ab2"). So, the # of good subseqs for f = 1 is 5 since we need to // exclude "". // // For f = 2, with 1 way to build "", choose any two 'b's to finalruct a // good subseq, so # of good subseqs = 1 + 1 * (2, 2) is 2 ("", "bb"). So, // the # of good subseqs for f = 2 = 1 since we need to exclude "". // // Therefore, the # of good subseqs for "aab" = 5 + 1 = 6. final int kMod = 1_000_000_007; int ans = 0; int[] count = new int[26]; for (final char c : s.toCharArray()) ++count[c - 'a']; final int maxFreq = Arrays.stream(count).max().getAsInt(); long[] fact = new long[maxFreq + 1]; long[] invFact = new long[maxFreq + 1]; getFactAndInvFact(maxFreq, kMod, fact, invFact); for (int freq = 1; freq <= maxFreq; ++freq) { long numSubseqs = 1; // "" for (final int charFreq : count) if (charFreq >= freq) numSubseqs = (numSubseqs + numSubseqs * nCk(charFreq, freq, fact, invFact, kMod)) % kMod; ans += numSubseqs - 1; // Minus "" ans %= kMod; } return (int) ans; } private int nCk(int n, int k, long[] fact, long[] invFact, int kMod) { return (int) (fact[n] * invFact[k] % kMod * invFact[n - k] % kMod); } private void getFactAndInvFact(int n, int kMod, long[] fact, long[] invFact) { long[] inv = new long[n + 1]; fact[0] = invFact[0] = 1; inv[0] = inv[1] = 1; for (int i = 1; i <= n; ++i) { if (i >= 2) inv[i] = kMod - kMod / i * inv[kMod % i] % kMod; fact[i] = fact[i - 1] * i % kMod; invFact[i] = invFact[i - 1] * inv[i] % kMod; } } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution: def countGoodSubsequences(self, s: str) -> int: kMod = 1_000_000_007 ans = 0 count = collections.Counter(s) @functools.lru_cache(None) def fact(i: int) -> int: if i == 1: return 1 return i * fact(i - 1) % kMod @functools.lru_cache(None) def invFact(i: int) -> int: if i <= 1: return 1 return pow(i, -1, kMod) * invFact(i - 1) % kMod @functools.lru_cache(None) def nCk(n: int, k: int) -> int: return fact(n) * invFact(k) * invFact(n - k) % kMod for freq in range(1, max(count.values()) + 1): numSubseqs = 1 # "" for charFreq in count.values(): if charFreq >= freq: numSubseqs = numSubseqs * (1 + nCk(charFreq, freq)) % kMod ans += numSubseqs - 1 # Minus "" ans %= kMod return ans