Problem

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.

Examples

Example 1

1
2
3

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2

1
2
3

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3

1
2

Input: n = 5
Output: 68

Solution

Method 1 – Dynamic Programming with State Transitions

Intuition

Each vowel can only follow certain other vowels, so we can use dynamic programming to count the number of valid strings ending with each vowel at each position. By updating the counts for each vowel according to the rules, we build up the answer for length n.

Approach

  1. Use five variables to represent the count of strings ending with each vowel at the current length.
  2. For each position from 2 to n, update the counts based on allowed transitions:
    • ‘a’ can follow ’e’, ‘i’, ‘u’
    • ’e’ can follow ‘a’, ‘i’
    • ‘i’ can follow ’e’, ‘o’
    • ‘o’ can follow ‘i’
    • ‘u’ can follow ‘i’, ‘o’
  3. Use modulo 10^9+7 for all operations.
  4. The answer is the sum of all counts at length n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int countVowelPermutation(int n) {
        const int MOD = 1e9+7;
        long a=1, e=1, i=1, o=1, u=1;
        for (int k=2; k<=n; ++k) {
            long na = (e+i+u)%MOD;
            long ne = (a+i)%MOD;
            long ni = (e+o)%MOD;
            long no = i%MOD;
            long nu = (i+o)%MOD;
            a=na; e=ne; i=ni; o=no; u=nu;
        }
        return (a+e+i+o+u)%MOD;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func countVowelPermutation(n int) int {
    const MOD = 1e9+7
    a, e, i, o, u := 1, 1, 1, 1, 1
    for k := 2; k <= n; k++ {
        na := (e + i + u) % MOD
        ne := (a + i) % MOD
        ni := (e + o) % MOD
        no := i % MOD
        nu := (i + o) % MOD
        a, e, i, o, u = na, ne, ni, no, nu
    }
    return (a + e + i + o + u) % MOD
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int countVowelPermutation(int n) {
        int MOD = 1000000007;
        long a=1, e=1, i=1, o=1, u=1;
        for (int k=2; k<=n; ++k) {
            long na = (e+i+u)%MOD;
            long ne = (a+i)%MOD;
            long ni = (e+o)%MOD;
            long no = i%MOD;
            long nu = (i+o)%MOD;
            a=na; e=ne; i=ni; o=no; u=nu;
        }
        return (int)((a+e+i+o+u)%MOD);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun countVowelPermutation(n: Int): Int {
        val MOD = 1000000007
        var a=1L; var e=1L; var i=1L; var o=1L; var u=1L
        for (k in 2..n) {
            val na = (e+i+u)%MOD
            val ne = (a+i)%MOD
            val ni = (e+o)%MOD
            val no = i%MOD
            val nu = (i+o)%MOD
            a=na; e=ne; i=ni; o=no; u=nu
        }
        return ((a+e+i+o+u)%MOD).toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def countVowelPermutation(n: int) -> int:
    MOD = 10**9+7
    a, e, i, o, u = 1, 1, 1, 1, 1
    for _ in range(2, n+1):
        na = (e + i + u) % MOD
        ne = (a + i) % MOD
        ni = (e + o) % MOD
        no = i % MOD
        nu = (i + o) % MOD
        a, e, i, o, u = na, ne, ni, no, nu
    return (a + e + i + o + u) % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn count_vowel_permutation(n: i32) -> i32 {
        let m = 1_000_000_007;
        let (mut a, mut e, mut i, mut o, mut u) = (1, 1, 1, 1, 1);
        for _ in 2..=n {
            let na = (e + i + u) % m;
            let ne = (a + i) % m;
            let ni = (e + o) % m;
            let no = i % m;
            let nu = (i + o) % m;
            a = na; e = ne; i = ni; o = no; u = nu;
        }
        (a + e + i + o + u) % m
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    countVowelPermutation(n: number): number {
        const MOD = 1e9+7;
        let a=1, e=1, i=1, o=1, u=1;
        for (let k=2; k<=n; ++k) {
            const na = (e+i+u)%MOD;
            const ne = (a+i)%MOD;
            const ni = (e+o)%MOD;
            const no = i%MOD;
            const nu = (i+o)%MOD;
            a=na; e=ne; i=ni; o=no; u=nu;
        }
        return (a+e+i+o+u)%MOD;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we iterate n times.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.

Method 2 -

Code

Complexity

  • Time: O(nnnxxxnnn)
  • Space: O(nnnxxx)