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 <= 104s consists of only lowercase English letters.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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
|
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
| 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;
}
}
|
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
| 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;
}
};
|
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
| 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
}
|
