Question

2539. Count the Number of Good Subsequences

中文文档

Description

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.

 

Example 1:

Input: s = "aabb"
Output: 11
Explanation: The total number of subsequences is 24. There are five subsequences which are not good: "aabb", "aabb", "aabb", "aabb", and the empty subsequence. Hence, the number of good subsequences is 24-5 = 11.

Example 2:

Input: s = "leet"
Output: 12
Explanation: There are four subsequences which are not good: "l_ee_t", "leet", "leet", and the empty subsequence. Hence, the number of good subsequences is 24-4 = 12.

Example 3:

Input: s = "abcd"
Output: 15
Explanation: All of the non-empty subsequences are good subsequences. Hence, the number of good subsequences is 24-1 = 15.

 

Constraints:

• 1 <= s.length <= 104
• s consists of only lowercase English letters.

Solutions

Solution 1

N = 10001
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
for i in range(1, N):
  f[i] = f[i - 1] * i % MOD
  g[i] = pow(f[i], MOD - 2, MOD)


def comb(n, k):
  return f[n] * g[k] * g[n - k] % MOD


class Solution:
  def countGoodSubsequences(self, s: str) -> int:
    cnt = Counter(s)
    ans = 0
    for i in range(1, max(cnt.values()) + 1):
      x = 1
      for v in cnt.values():
        if v >= i:
          x = x * (comb(v, i) + 1) % MOD
      ans = (ans + x - 1) % MOD
    return ans

class Solution {
  private static final int N = 10001;
  private static final int MOD = (int) 1e9 + 7;
  private static final long[] F = new long[N];
  private static final long[] G = new long[N];

  static {
    F[0] = 1;
    G[0] = 1;
    for (int i = 1; i < N; ++i) {
      F[i] = F[i - 1] * i % MOD;
      G[i] = qmi(F[i], MOD - 2, MOD);
    }
  }

  public static long qmi(long a, long k, long p) {
    long res = 1;
    while (k != 0) {
      if ((k & 1) == 1) {
        res = res * a % p;
      }
      k >>= 1;
      a = a * a % p;
    }
    return res;
  }

  public static long comb(int n, int k) {
    return (F[n] * G[k] % MOD) * G[n - k] % MOD;
  }

  public int countGoodSubsequences(String s) {
    int[] cnt = new int[26];
    int mx = 1;
    for (int i = 0; i < s.length(); ++i) {
      mx = Math.max(mx, ++cnt[s.charAt(i) - 'a']);
    }
    long ans = 0;
    for (int i = 1; i <= mx; ++i) {
      long x = 1;
      for (int j = 0; j < 26; ++j) {
        if (cnt[j] >= i) {
          x = x * (comb(cnt[j], i) + 1) % MOD;
        }
      }
      ans = (ans + x - 1) % MOD;
    }
    return (int) ans;
  }
}

int N = 10001;
int MOD = 1e9 + 7;
long f[10001];
long g[10001];

long qmi(long a, long k, long p) {
  long res = 1;
  while (k != 0) {
    if ((k & 1) == 1) {
      res = res * a % p;
    }
    k >>= 1;
    a = a * a % p;
  }
  return res;
}

int init = []() {
  f[0] = 1;
  g[0] = 1;
  for (int i = 1; i < N; ++i) {
    f[i] = f[i - 1] * i % MOD;
    g[i] = qmi(f[i], MOD - 2, MOD);
  }
  return 0;
}();

int comb(int n, int k) {
  return (f[n] * g[k] % MOD) * g[n - k] % MOD;
}

class Solution {
public:
  int countGoodSubsequences(string s) {
    int cnt[26]{};
    int mx = 1;
    for (char& c : s) {
      mx = max(mx, ++cnt[c - 'a']);
    }
    long ans = 0;
    for (int i = 1; i <= mx; ++i) {
      long x = 1;
      for (int j = 0; j < 26; ++j) {
        if (cnt[j] >= i) {
          x = (x * (comb(cnt[j], i) + 1)) % MOD;
        }
      }
      ans = (ans + x - 1) % MOD;
    }
    return ans;
  }
};

const n = 1e4 + 1
const mod = 1e9 + 7

var f = make([]int, n)
var g = make([]int, n)

func qmi(a, k, p int) int {
  res := 1
  for k != 0 {
    if k&1 == 1 {
      res = res * a % p
    }
    k >>= 1
    a = a * a % p
  }
  return res
}

func init() {
  f[0], g[0] = 1, 1
  for i := 1; i < n; i++ {
    f[i] = f[i-1] * i % mod
    g[i] = qmi(f[i], mod-2, mod)
  }
}

func comb(n, k int) int {
  return (f[n] * g[k] % mod) * g[n-k] % mod
}

func countGoodSubsequences(s string) (ans int) {
  cnt := [26]int{}
  mx := 1
  for _, c := range s {
    cnt[c-'a']++
    mx = max(mx, cnt[c-'a'])
  }
  for i := 1; i <= mx; i++ {
    x := 1
    for _, v := range cnt {
      if v >= i {
        x = (x * (comb(v, i) + 1)) % mod
      }
    }
    ans = (ans + x - 1) % mod
  }
  return
}