Dynamic Programming
Description
Given an integer n
, your task is to count how many strings of length n
can be formed under the following rules:
Each character is a lower case vowel ('a'
, 'e'
, 'i'
, 'o'
, 'u'
)
Each vowel 'a'
may only be followed by an 'e'
.
Each vowel 'e'
may only be followed by an 'a'
or an 'i'
.
Each vowel 'i'
may not be followed by another 'i'
.
Each vowel 'o'
may only be followed by an 'i'
or a 'u'
.
Each vowel 'u'
may only be followed by an 'a'
.
Since the answer may be too large, return it modulo 10^9 + 7
.
Example 1:
Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".
Example 2:
Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".
Example 3:
Input: n = 5
Output: 68
Constraints:
Solutions
Solution 1: Dynamic Programming
Based on the problem description, we can list the possible subsequent vowels for each vowel:
a [ e]
e [ a| i]
i [ a| e| o| u]
o [ i| u]
u [ a]
From this, we can deduce the possible preceding vowels for each vowel:
[ e| i| u] a
[ a| i] e
[ e| o] i
[ i] o
[ i| o] u
We define $f[i]$ as the number of strings of the current length ending with the $i$-th vowel. If the length is $1$, then $f[i]=1$.
When the length is greater than $1$, we define $g[i]$ as the number of strings of the current length ending with the $i$-th vowel. Then $g[i]$ can be derived from $f$, that is:
$$
g[i]=
\begin{cases}
f[1]+f[2]+f[4] & i=0 \
f[0]+f[2] & i=1 \
f[1]+f[3] & i=2 \
f[2] & i=3 \
f[2]+f[3] & i=4
\end{cases}
$$
The final answer is $\sum_{i=0}^{4}f[i]$. Note that the answer may be very large, so we need to take the modulus of $10^9+7$.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string, and $C$ is the number of vowels. In this problem, $C=5$.
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def countVowelPermutation ( self , n : int ) -> int :
f = [ 1 ] * 5
mod = 10 ** 9 + 7
for _ in range ( n - 1 ):
g = [ 0 ] * 5
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod
g [ 3 ] = f [ 2 ]
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod
f = g
return sum ( f ) % mod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public int countVowelPermutation ( int n ) {
long [] f = new long [ 5 ] ;
Arrays . fill ( f , 1 );
final int mod = ( int ) 1e9 + 7 ;
for ( int i = 1 ; i < n ; ++ i ) {
long [] g = new long [ 5 ] ;
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ] ) % mod ;
g [ 1 ] = ( f [ 0 ] + f [ 2 ] ) % mod ;
g [ 2 ] = ( f [ 1 ] + f [ 3 ] ) % mod ;
g [ 3 ] = f [ 2 ] ;
g [ 4 ] = ( f [ 2 ] + f [ 3 ] ) % mod ;
f = g ;
}
long ans = 0 ;
for ( long x : f ) {
ans = ( ans + x ) % mod ;
}
return ( int ) ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public :
int countVowelPermutation ( int n ) {
using ll = long long ;
vector < ll > f ( 5 , 1 );
const int mod = 1e9 + 7 ;
for ( int i = 1 ; i < n ; ++ i ) {
vector < ll > g ( 5 );
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod ;
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod ;
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod ;
g [ 3 ] = f [ 2 ];
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod ;
f = move ( g );
}
return accumulate ( f . begin (), f . end (), 0L L ) % mod ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 func countVowelPermutation ( n int ) ( ans int ) {
const mod int = 1e9 + 7
f := make ([] int , 5 )
for i := range f {
f [ i ] = 1
}
for i := 1 ; i < n ; i ++ {
g := make ([] int , 5 )
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod
g [ 3 ] = f [ 2 ] % mod
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod
f = g
}
for _ , x := range f {
ans = ( ans + x ) % mod
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 function countVowelPermutation ( n : number ) : number {
const f : number [] = Array ( 5 ). fill ( 1 );
const mod = 1e9 + 7 ;
for ( let i = 1 ; i < n ; ++ i ) {
const g : number [] = Array ( 5 ). fill ( 0 );
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod ;
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod ;
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod ;
g [ 3 ] = f [ 2 ];
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod ;
f . splice ( 0 , 5 , ... g );
}
return f . reduce (( a , b ) => ( a + b ) % mod );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 /**
* @param {number} n
* @return {number}
*/
var countVowelPermutation = function ( n ) {
const mod = 1e9 + 7 ;
const f = Array ( 5 ). fill ( 1 );
for ( let i = 1 ; i < n ; ++ i ) {
const g = Array ( 5 ). fill ( 0 );
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod ;
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod ;
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod ;
g [ 3 ] = f [ 2 ];
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod ;
f . splice ( 0 , 5 , ... g );
}
return f . reduce (( a , b ) => ( a + b ) % mod );
};
Solution 2: Matrix Exponentiation to Accelerate Recursion
The time complexity is $O(C^3 \times \log n)$, and the space complexity is $O(C^2)$. Here, $C$ is the number of vowels. In this problem, $C=5$.
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 import numpy as np
class Solution :
def countVowelPermutation ( self , n : int ) -> int :
mod = 10 ** 9 + 7
factor = np . asmatrix (
[
( 0 , 1 , 0 , 0 , 0 ),
( 1 , 0 , 1 , 0 , 0 ),
( 1 , 1 , 0 , 1 , 1 ),
( 0 , 0 , 1 , 0 , 1 ),
( 1 , 0 , 0 , 0 , 0 ),
],
np . dtype ( "O" ),
)
res = np . asmatrix ([( 1 , 1 , 1 , 1 , 1 )], np . dtype ( "O" ))
n -= 1
while n :
if n & 1 :
res = res * factor % mod
factor = factor * factor % mod
n >>= 1
return res . sum () % 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
37
38
39
40 class Solution {
private final int mod = ( int ) 1e9 + 7 ;
public int countVowelPermutation ( int n ) {
long [][] a
= {{ 0 , 1 , 0 , 0 , 0 }, { 1 , 0 , 1 , 0 , 0 }, { 1 , 1 , 0 , 1 , 1 }, { 0 , 0 , 1 , 0 , 1 }, { 1 , 0 , 0 , 0 , 0 }};
long [][] res = pow ( a , n - 1 );
long ans = 0 ;
for ( long x : res [ 0 ] ) {
ans = ( ans + x ) % mod ;
}
return ( int ) ans ;
}
private long [][] mul ( long [][] a , long [][] b ) {
int m = a . length , n = b [ 0 ] . length ;
long [][] c = new long [ m ][ n ] ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
for ( int k = 0 ; k < b . length ; ++ k ) {
c [ i ][ j ] = ( c [ i ][ j ] + a [ i ][ k ] * b [ k ][ j ] ) % mod ;
}
}
}
return c ;
}
private long [][] pow ( long [][] a , int n ) {
long [][] res = new long [ 1 ][ a . length ] ;
Arrays . fill ( res [ 0 ] , 1 );
while ( n > 0 ) {
if (( n & 1 ) == 1 ) {
res = mul ( res , a );
}
a = mul ( a , a );
n >>= 1 ;
}
return res ;
}
}
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 class Solution {
public :
int countVowelPermutation ( int n ) {
vector < vector < ll >> a = {
{ 0 , 1 , 0 , 0 , 0 },
{ 1 , 0 , 1 , 0 , 0 },
{ 1 , 1 , 0 , 1 , 1 },
{ 0 , 0 , 1 , 0 , 1 },
{ 1 , 0 , 0 , 0 , 0 }};
vector < vector < ll >> res = pow ( a , n - 1 );
return accumulate ( res [ 0 ]. begin (), res [ 0 ]. end (), 0L L ) % mod ;
}
private :
using ll = long long ;
const int mod = 1e9 + 7 ;
vector < vector < ll >> mul ( vector < vector < ll >>& a , vector < vector < ll >>& b ) {
int m = a . size (), n = b [ 0 ]. size ();
vector < vector < ll >> c ( m , vector < ll > ( n ));
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
for ( int k = 0 ; k < b . size (); ++ k ) {
c [ i ][ j ] = ( c [ i ][ j ] + a [ i ][ k ] * b [ k ][ j ]) % mod ;
}
}
}
return c ;
}
vector < vector < ll >> pow ( vector < vector < ll >>& a , int n ) {
vector < vector < ll >> res ;
res . push_back ({ 1 , 1 , 1 , 1 , 1 });
while ( n ) {
if ( n & 1 ) {
res = mul ( res , a );
}
a = mul ( a , a );
n >>= 1 ;
}
return res ;
}
};
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 const mod = 1e9 + 7
func countVowelPermutation ( n int ) ( ans int ) {
a := [][] int {
{ 0 , 1 , 0 , 0 , 0 },
{ 1 , 0 , 1 , 0 , 0 },
{ 1 , 1 , 0 , 1 , 1 },
{ 0 , 0 , 1 , 0 , 1 },
{ 1 , 0 , 0 , 0 , 0 }}
res := pow ( a , n - 1 )
for _ , x := range res [ 0 ] {
ans = ( ans + x ) % mod
}
return
}
func mul ( a , b [][] int ) [][] int {
m , n := len ( a ), len ( b [ 0 ])
c := make ([][] int , m )
for i := range c {
c [ i ] = make ([] int , n )
}
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
for k := 0 ; k < len ( b ); k ++ {
c [ i ][ j ] = ( c [ i ][ j ] + a [ i ][ k ] * b [ k ][ j ]) % mod
}
}
}
return c
}
func pow ( a [][] int , n int ) [][] int {
res := [][] int {{ 1 , 1 , 1 , 1 , 1 }}
for n > 0 {
if n & 1 == 1 {
res = mul ( res , a )
}
a = mul ( a , a )
n >>= 1
}
return res
}
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 const mod = 1e9 + 7 ;
function countVowelPermutation ( n : number ) : number {
const a : number [][] = [
[ 0 , 1 , 0 , 0 , 0 ],
[ 1 , 0 , 1 , 0 , 0 ],
[ 1 , 1 , 0 , 1 , 1 ],
[ 0 , 0 , 1 , 0 , 1 ],
[ 1 , 0 , 0 , 0 , 0 ],
];
const res = pow ( a , n - 1 );
return res [ 0 ]. reduce (( a , b ) => ( a + b ) % mod );
}
function mul ( a : number [][], b : number [][]) : number [][] {
const [ m , n ] = [ a . length , b [ 0 ]. length ];
const c = Array . from ({ length : m }, () => Array . from ({ length : n }, () => 0 ));
for ( let i = 0 ; i < m ; ++ i ) {
for ( let j = 0 ; j < n ; ++ j ) {
for ( let k = 0 ; k < b . length ; ++ k ) {
c [ i ][ j ] =
( c [ i ][ j ] + Number (( BigInt ( a [ i ][ k ]) * BigInt ( b [ k ][ j ])) % BigInt ( mod ))) % mod ;
}
}
}
return c ;
}
function pow ( a : number [][], n : number ) : number [][] {
let res : number [][] = [[ 1 , 1 , 1 , 1 , 1 ]];
while ( n ) {
if ( n & 1 ) {
res = mul ( res , a );
}
a = mul ( a , a );
n >>>= 1 ;
}
return res ;
}
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 /**
* @param {number} n
* @return {number}
*/
const mod = 1e9 + 7 ;
var countVowelPermutation = function ( n ) {
const a = [
[ 0 , 1 , 0 , 0 , 0 ],
[ 1 , 0 , 1 , 0 , 0 ],
[ 1 , 1 , 0 , 1 , 1 ],
[ 0 , 0 , 1 , 0 , 1 ],
[ 1 , 0 , 0 , 0 , 0 ],
];
const res = pow ( a , n - 1 );
return res [ 0 ]. reduce (( a , b ) => ( a + b ) % mod );
};
function mul ( a , b ) {
const [ m , n ] = [ a . length , b [ 0 ]. length ];
const c = Array . from ({ length : m }, () => Array . from ({ length : n }, () => 0 ));
for ( let i = 0 ; i < m ; ++ i ) {
for ( let j = 0 ; j < n ; ++ j ) {
for ( let k = 0 ; k < b . length ; ++ k ) {
c [ i ][ j ] =
( c [ i ][ j ] + Number (( BigInt ( a [ i ][ k ]) * BigInt ( b [ k ][ j ])) % BigInt ( mod ))) % mod ;
}
}
}
return c ;
}
function pow ( a , n ) {
let res = [[ 1 , 1 , 1 , 1 , 1 ]];
while ( n ) {
if ( n & 1 ) {
res = mul ( res , a );
}
a = mul ( a , a );
n >>>= 1 ;
}
return res ;
}