##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2539.html

# 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: "leet", "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

• 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;
}
}

• 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


• 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
}

func max(a, b int) int {
if a > b {
return a
}
return b
}