1220. Count Vowels Permutation
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
From: LeetCode
Link: 1220. Count Vowels Permutation
Solution:
Ideas:
keep counts of strings ending with each vowel, then update by reverse rules.
Code:
intcountVowelPermutation(intn){constlongMOD=1000000007;longa=1,e=1,i=1,o=1,u=1;for(intlen=2;len<=n;len++){longna=(e+i+u)%MOD;// previous e/i/u can go to alongne=(a+i)%MOD;// previous a/i can go to elongni=(e+o)%MOD;// previous e/o can go to ilongno=i%MOD;// previous i can go to olongnu=(i+o)%MOD;// previous i/o can go to ua=na;e=ne;i=ni;o=no;u=nu;}return(int)((a+e+i+o+u)%MOD);}
