Hash Table
Math
String
Combinatorics
Counting
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: "aab b", "aabb ", "a abb ", "aa bb ", 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
Python3 Java C++ Go
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
}
GitHub