Skip to content

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<int> 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<long>& fact, const vector<long>& invFact,
          int kMod) {
    return fact[n] * invFact[k] % kMod * invFact[n - k] % kMod;
  }

  pair<vector<long>, vector<long>> getFactAndInvFact(int n, int kMod) {
    vector<long> fact(n + 1);
    vector<long> invFact(n + 1);
    vector<long> 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