Welcome to Subscribe On Youtube

1220. Count Vowels Permutation

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:

• 1 <= n <= 2 * 10^4

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$.

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$.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript

• 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;
      }
  }
  

• 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(), 0LL) % mod;
      }
  };
  

• 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
  
  

• 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
  }
  

• 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);
  }
  
  

• /**
   * @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);
  };
  
  

All Problems

All Solutions