String
Dynamic Programming
Description
Given a string s, return the number of distinct non-empty subsequences of s
. Since the answer may be very large, return it modulo 109 + 7
.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace"
is a subsequence of "a bc de "
while "aec"
is not.
Example 1:
Input: s = "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
Example 2:
Input: s = "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".
Example 3:
Input: s = "aaa"
Output: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".
Constraints:
1 <= s.length <= 2000
s
consists of lowercase English letters.
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust C
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def distinctSubseqII ( self , s : str ) -> int :
mod = 10 ** 9 + 7
n = len ( s )
dp = [[ 0 ] * 26 for _ in range ( n + 1 )]
for i , c in enumerate ( s , 1 ):
k = ord ( c ) - ord ( 'a' )
for j in range ( 26 ):
if j == k :
dp [ i ][ j ] = sum ( dp [ i - 1 ]) % mod + 1
else :
dp [ i ][ j ] = dp [ i - 1 ][ j ]
return sum ( dp [ - 1 ]) % mod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
private static final int MOD = ( int ) 1e9 + 7 ;
public int distinctSubseqII ( String s ) {
int [] dp = new int [ 26 ] ;
for ( int i = 0 ; i < s . length (); ++ i ) {
int j = s . charAt ( i ) - 'a' ;
dp [ j ] = sum ( dp ) + 1 ;
}
return sum ( dp );
}
private int sum ( int [] arr ) {
int x = 0 ;
for ( int v : arr ) {
x = ( x + v ) % MOD ;
}
return x ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public :
const int mod = 1e9 + 7 ;
int distinctSubseqII ( string s ) {
vector < long > dp ( 26 );
for ( char & c : s ) {
int i = c - 'a' ;
dp [ i ] = accumulate ( dp . begin (), dp . end (), 1l ) % mod ;
}
return accumulate ( dp . begin (), dp . end (), 0l ) % mod ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 func distinctSubseqII ( s string ) int {
const mod int = 1e9 + 7
sum := func ( arr [] int ) int {
x := 0
for _ , v := range arr {
x = ( x + v ) % mod
}
return x
}
dp := make ([] int , 26 )
for _ , c := range s {
c -= 'a'
dp [ c ] = sum ( dp ) + 1
}
return sum ( dp )
}
function distinctSubseqII ( s : string ) : number {
const mod = 1e9 + 7 ;
const dp = new Array ( 26 ). fill ( 0 );
for ( const c of s ) {
dp [ c . charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 )] = dp . reduce (( r , v ) => ( r + v ) % mod , 0 ) + 1 ;
}
return dp . reduce (( r , v ) => ( r + v ) % mod , 0 );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 impl Solution {
pub fn distinct_subseq_ii ( s : String ) -> i32 {
const MOD : i32 = ( 1e9 as i32 ) + 7 ;
let mut dp = [ 0 ; 26 ];
for u in s . as_bytes () {
let i = ( u - & b'a' ) as usize ;
dp [ i ] = ({
let mut sum = 0 ;
dp . iter (). for_each ( |& v | {
sum = ( sum + v ) % MOD ;
});
sum
}) + 1 ;
}
let mut res = 0 ;
dp . iter (). for_each ( |& v | {
res = ( res + v ) % MOD ;
});
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 int distinctSubseqII ( char * s ) {
int mod = 1e9 + 7 ;
int n = strlen ( s );
int dp [ 26 ] = { 0 };
for ( int i = 0 ; i < n ; i ++ ) {
int sum = 0 ;
for ( int j = 0 ; j < 26 ; j ++ ) {
sum = ( sum + dp [ j ]) % mod ;
}
dp [ s [ i ] - 'a' ] = sum + 1 ;
}
int res = 0 ;
for ( int i = 0 ; i < 26 ; i ++ ) {
res = ( res + dp [ i ]) % mod ;
}
return res ;
}
Solution 2
Solution 3