String
Dynamic Programming
Description
Given a string of digits s
, return the number of palindromic subsequences of s
having length 5
. Since the answer may be very large, return it modulo 109 + 7
.
Note:
A string is palindromic if it reads the same forward and backward.
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 = "103301"
Output: 2
Explanation:
There are 6 possible subsequences of length 5: "10330","10331","10301","10301","13301","03301".
Two of them (both equal to "10301") are palindromic.
Example 2:
Input: s = "0000000"
Output: 21
Explanation: All 21 subsequences are "00000", which is palindromic.
Example 3:
Input: s = "9999900000"
Output: 2
Explanation: The only two palindromic subsequences are "99999" and "00000".
Constraints:
1 <= s.length <= 104
s
consists of digits.
Solutions
Solution 1: Enumeration + Counting
The time complexity is $O(100 \times n)$, and the space complexity is $O(100 \times n)$. Where $n$ is the length of the string $s$.
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
25
26
27
28
29
30
31 class Solution :
def countPalindromes ( self , s : str ) -> int :
mod = 10 ** 9 + 7
n = len ( s )
pre = [[[ 0 ] * 10 for _ in range ( 10 )] for _ in range ( n + 2 )]
suf = [[[ 0 ] * 10 for _ in range ( 10 )] for _ in range ( n + 2 )]
t = list ( map ( int , s ))
c = [ 0 ] * 10
for i , v in enumerate ( t , 1 ):
for j in range ( 10 ):
for k in range ( 10 ):
pre [ i ][ j ][ k ] = pre [ i - 1 ][ j ][ k ]
for j in range ( 10 ):
pre [ i ][ j ][ v ] += c [ j ]
c [ v ] += 1
c = [ 0 ] * 10
for i in range ( n , 0 , - 1 ):
v = t [ i - 1 ]
for j in range ( 10 ):
for k in range ( 10 ):
suf [ i ][ j ][ k ] = suf [ i + 1 ][ j ][ k ]
for j in range ( 10 ):
suf [ i ][ j ][ v ] += c [ j ]
c [ v ] += 1
ans = 0
for i in range ( 1 , n + 1 ):
for j in range ( 10 ):
for k in range ( 10 ):
ans += pre [ i - 1 ][ j ][ k ] * suf [ i + 1 ][ j ][ k ]
ans %= 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 class Solution {
private static final int MOD = ( int ) 1e9 + 7 ;
public int countPalindromes ( String s ) {
int n = s . length ();
int [][][] pre = new int [ n + 2 ][ 10 ][ 10 ] ;
int [][][] suf = new int [ n + 2 ][ 10 ][ 10 ] ;
int [] t = new int [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
t [ i ] = s . charAt ( i ) - '0' ;
}
int [] c = new int [ 10 ] ;
for ( int i = 1 ; i <= n ; ++ i ) {
int v = t [ i - 1 ] ;
for ( int j = 0 ; j < 10 ; ++ j ) {
for ( int k = 0 ; k < 10 ; ++ k ) {
pre [ i ][ j ][ k ] = pre [ i - 1 ][ j ][ k ] ;
}
}
for ( int j = 0 ; j < 10 ; ++ j ) {
pre [ i ][ j ][ v ] += c [ j ] ;
}
c [ v ]++ ;
}
c = new int [ 10 ] ;
for ( int i = n ; i > 0 ; -- i ) {
int v = t [ i - 1 ] ;
for ( int j = 0 ; j < 10 ; ++ j ) {
for ( int k = 0 ; k < 10 ; ++ k ) {
suf [ i ][ j ][ k ] = suf [ i + 1 ][ j ][ k ] ;
}
}
for ( int j = 0 ; j < 10 ; ++ j ) {
suf [ i ][ j ][ v ] += c [ j ] ;
}
c [ v ]++ ;
}
long ans = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 0 ; j < 10 ; ++ j ) {
for ( int k = 0 ; k < 10 ; ++ k ) {
ans += ( long ) pre [ i - 1 ][ j ][ k ] * suf [ i + 1 ][ j ][ k ] ;
ans %= 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 class Solution {
public :
const int mod = 1e9 + 7 ;
int countPalindromes ( string s ) {
int n = s . size ();
int pre [ n + 2 ][ 10 ][ 10 ];
int suf [ n + 2 ][ 10 ][ 10 ];
memset ( pre , 0 , sizeof pre );
memset ( suf , 0 , sizeof suf );
int t [ n ];
for ( int i = 0 ; i < n ; ++ i ) t [ i ] = s [ i ] - '0' ;
int c [ 10 ] = { 0 };
for ( int i = 1 ; i <= n ; ++ i ) {
int v = t [ i - 1 ];
for ( int j = 0 ; j < 10 ; ++ j ) {
for ( int k = 0 ; k < 10 ; ++ k ) {
pre [ i ][ j ][ k ] = pre [ i - 1 ][ j ][ k ];
}
}
for ( int j = 0 ; j < 10 ; ++ j ) {
pre [ i ][ j ][ v ] += c [ j ];
}
c [ v ] ++ ;
}
memset ( c , 0 , sizeof c );
for ( int i = n ; i > 0 ; -- i ) {
int v = t [ i - 1 ];
for ( int j = 0 ; j < 10 ; ++ j ) {
for ( int k = 0 ; k < 10 ; ++ k ) {
suf [ i ][ j ][ k ] = suf [ i + 1 ][ j ][ k ];
}
}
for ( int j = 0 ; j < 10 ; ++ j ) {
suf [ i ][ j ][ v ] += c [ j ];
}
c [ v ] ++ ;
}
long ans = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 0 ; j < 10 ; ++ j ) {
for ( int k = 0 ; k < 10 ; ++ k ) {
ans += 1l l * pre [ i - 1 ][ j ][ k ] * suf [ i + 1 ][ j ][ k ];
ans %= 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 func countPalindromes ( s string ) int {
n := len ( s )
pre := [ 10010 ][ 10 ][ 10 ] int {}
suf := [ 10010 ][ 10 ][ 10 ] int {}
t := make ([] int , n )
for i , c := range s {
t [ i ] = int ( c - '0' )
}
c := [ 10 ] int {}
for i := 1 ; i <= n ; i ++ {
v := t [ i - 1 ]
for j := 0 ; j < 10 ; j ++ {
for k := 0 ; k < 10 ; k ++ {
pre [ i ][ j ][ k ] = pre [ i - 1 ][ j ][ k ]
}
}
for j := 0 ; j < 10 ; j ++ {
pre [ i ][ j ][ v ] += c [ j ]
}
c [ v ] ++
}
c = [ 10 ] int {}
for i := n ; i > 0 ; i -- {
v := t [ i - 1 ]
for j := 0 ; j < 10 ; j ++ {
for k := 0 ; k < 10 ; k ++ {
suf [ i ][ j ][ k ] = suf [ i + 1 ][ j ][ k ]
}
}
for j := 0 ; j < 10 ; j ++ {
suf [ i ][ j ][ v ] += c [ j ]
}
c [ v ] ++
}
ans := 0
const mod int = 1e9 + 7
for i := 1 ; i <= n ; i ++ {
for j := 0 ; j < 10 ; j ++ {
for k := 0 ; k < 10 ; k ++ {
ans += pre [ i - 1 ][ j ][ k ] * suf [ i + 1 ][ j ][ k ]
ans %= mod
}
}
}
return ans
}
GitHub