String
Dynamic Programming
Description
Given a string s, return the number of different non-empty palindromic subsequences in s
. Since the answer may be very large, return it modulo 109 + 7
.
A subsequence of a string is obtained by deleting zero or more characters from the string.
A sequence is palindromic if it is equal to the sequence reversed.
Two sequences a1 , a2 , ...
and b1 , b2 , ...
are different if there is some i
for which ai != bi
.
Example 1:
Input: s = "bccb"
Output: 6
Explanation: The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.
Example 2:
Input: s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
Output: 104860361
Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 109 + 7.
Constraints:
1 <= s.length <= 1000
s[i]
is either 'a'
, 'b'
, 'c'
, or 'd'
.
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 class Solution :
def countPalindromicSubsequences ( self , s : str ) -> int :
mod = 10 ** 9 + 7
n = len ( s )
dp = [[[ 0 ] * 4 for _ in range ( n )] for _ in range ( n )]
for i , c in enumerate ( s ):
dp [ i ][ i ][ ord ( c ) - ord ( 'a' )] = 1
for l in range ( 2 , n + 1 ):
for i in range ( n - l + 1 ):
j = i + l - 1
for c in 'abcd' :
k = ord ( c ) - ord ( 'a' )
if s [ i ] == s [ j ] == c :
dp [ i ][ j ][ k ] = 2 + sum ( dp [ i + 1 ][ j - 1 ])
elif s [ i ] == c :
dp [ i ][ j ][ k ] = dp [ i ][ j - 1 ][ k ]
elif s [ j ] == c :
dp [ i ][ j ][ k ] = dp [ i + 1 ][ j ][ k ]
else :
dp [ i ][ j ][ k ] = dp [ i + 1 ][ j - 1 ][ k ]
return sum ( dp [ 0 ][ - 1 ]) % mod
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 class Solution {
private final int MOD = ( int ) 1e9 + 7 ;
public int countPalindromicSubsequences ( String s ) {
int n = s . length ();
long [][][] dp = new long [ n ][ n ][ 4 ] ;
for ( int i = 0 ; i < n ; ++ i ) {
dp [ i ][ i ][ s . charAt ( i ) - 'a' ] = 1 ;
}
for ( int l = 2 ; l <= n ; ++ l ) {
for ( int i = 0 ; i + l <= n ; ++ i ) {
int j = i + l - 1 ;
for ( char c = 'a' ; c <= 'd' ; ++ c ) {
int k = c - 'a' ;
if ( s . charAt ( i ) == c && s . charAt ( j ) == c ) {
dp [ i ][ j ][ k ] = 2 + dp [ i + 1 ][ j - 1 ][ 0 ] + dp [ i + 1 ][ j - 1 ][ 1 ]
+ dp [ i + 1 ][ j - 1 ][ 2 ] + dp [ i + 1 ][ j - 1 ][ 3 ] ;
dp [ i ][ j ][ k ] %= MOD ;
} else if ( s . charAt ( i ) == c ) {
dp [ i ][ j ][ k ] = dp [ i ][ j - 1 ][ k ] ;
} else if ( s . charAt ( j ) == c ) {
dp [ i ][ j ][ k ] = dp [ i + 1 ][ j ][ k ] ;
} else {
dp [ i ][ j ][ k ] = dp [ i + 1 ][ j - 1 ][ k ] ;
}
}
}
}
long ans = 0 ;
for ( int k = 0 ; k < 4 ; ++ k ) {
ans += dp [ 0 ][ n - 1 ][ k ] ;
}
return ( int ) ( ans % MOD );
}
}
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 using ll = long long ;
class Solution {
public :
int countPalindromicSubsequences ( string s ) {
int mod = 1e9 + 7 ;
int n = s . size ();
vector < vector < vector < ll >>> dp ( n , vector < vector < ll >> ( n , vector < ll > ( 4 )));
for ( int i = 0 ; i < n ; ++ i ) dp [ i ][ i ][ s [ i ] - 'a' ] = 1 ;
for ( int l = 2 ; l <= n ; ++ l ) {
for ( int i = 0 ; i + l <= n ; ++ i ) {
int j = i + l - 1 ;
for ( char c = 'a' ; c <= 'd' ; ++ c ) {
int k = c - 'a' ;
if ( s [ i ] == c && s [ j ] == c )
dp [ i ][ j ][ k ] = 2 + accumulate ( dp [ i + 1 ][ j - 1 ]. begin (), dp [ i + 1 ][ j - 1 ]. end (), 0l l ) % mod ;
else if ( s [ i ] == c )
dp [ i ][ j ][ k ] = dp [ i ][ j - 1 ][ k ];
else if ( s [ j ] == c )
dp [ i ][ j ][ k ] = dp [ i + 1 ][ j ][ k ];
else
dp [ i ][ j ][ k ] = dp [ i + 1 ][ j - 1 ][ k ];
}
}
}
ll ans = accumulate ( dp [ 0 ][ n - 1 ]. begin (), dp [ 0 ][ n - 1 ]. end (), 0l l );
return ( int ) ( ans % mod );
}
};
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 func countPalindromicSubsequences ( s string ) int {
mod := int ( 1e9 ) + 7
n := len ( s )
dp := make ([][][] int , n )
for i := range dp {
dp [ i ] = make ([][] int , n )
for j := range dp [ i ] {
dp [ i ][ j ] = make ([] int , 4 )
}
}
for i , c := range s {
dp [ i ][ i ][ c - 'a' ] = 1
}
for l := 2 ; l <= n ; l ++ {
for i := 0 ; i + l <= n ; i ++ {
j := i + l - 1
for _ , c := range [ 4 ] byte { 'a' , 'b' , 'c' , 'd' } {
k := int ( c - 'a' )
if s [ i ] == c && s [ j ] == c {
dp [ i ][ j ][ k ] = 2 + ( dp [ i + 1 ][ j - 1 ][ 0 ] + dp [ i + 1 ][ j - 1 ][ 1 ] + dp [ i + 1 ][ j - 1 ][ 2 ] + dp [ i + 1 ][ j - 1 ][ 3 ]) % mod
} else if s [ i ] == c {
dp [ i ][ j ][ k ] = dp [ i ][ j - 1 ][ k ]
} else if s [ j ] == c {
dp [ i ][ j ][ k ] = dp [ i + 1 ][ j ][ k ]
} else {
dp [ i ][ j ][ k ] = dp [ i + 1 ][ j - 1 ][ k ]
}
}
}
}
ans := 0
for _ , v := range dp [ 0 ][ n - 1 ] {
ans += v
}
return ans % mod
}
GitHub