Count Vowels Permutation
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This problem exhibits optimal substructure and overlapping subproblems, making it a classic candidate for dynamic programming. We can solve it by building up the counts for strings of length i from the counts for strings of length i-1. A 2D array can be used to store the number of valid strings of a certain length ending with a specific vowel.
Algorithm
- Create a 2D array
dpof size(n + 1) x 5, wheredp[i][j]stores the number of valid strings of lengthiending with thej-th vowel. - Base Case: For strings of length 1, all vowels are possible. Initialize
dp[1][j] = 1for alljfrom 0 to 4 (representing 'a' through 'u'). - Recurrence Relation: For
ifrom 2 ton, calculatedp[i][j]based on the values indp[i-1]. The rules for which vowel can precede another define the transitions:dp[i][a] = (dp[i-1][e] + dp[i-1][i] + dp[i-1][u]) % MODdp[i][e] = (dp[i-1][a] + dp[i-1][i]) % MODdp[i][i] = (dp[i-1][e] + dp[i-1][o]) % MODdp[i][o] = dp[i-1][i] % MODdp[i][u] = (dp[i-1][i] + dp[i-1][o]) % MOD
- Result: The total count is the sum of all values in the last row,
dp[n]. Sumdp[n][j]for alljand take the final modulo.
Walkthrough
We define dp[i][j] as the number of valid strings of length i that end with the j-th vowel (where 0='a', 1='e', 2='i', 3='o', 4='u'). To find the number of strings of length i ending in a vowel, say 'a', we need to sum up the counts of strings of length i-1 that could validly precede 'a'. According to the rules, 'a' can be preceded by 'e', 'i', or 'u'. This logic gives us a set of recurrence relations that we can use to fill our DP table from the base case (length 1) up to the desired length n.
class Solution { public int countVowelPermutation(int n) { int MOD = 1_000_000_007; // 0:a, 1:e, 2:i, 3:o, 4:u long[][] dp = new long[n + 1][5]; // Base case: for n = 1, each vowel is a valid string of length 1 for (int j = 0; j < 5; j++) { dp[1][j] = 1; } // Fill DP table for lengths from 2 to n for (int i = 2; i <= n; i++) { // Strings ending in 'a' must be preceded by 'e', 'i', or 'u' dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % MOD; // Strings ending in 'e' must be preceded by 'a' or 'i' dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; // Strings ending in 'i' must be preceded by 'e' or 'o' dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % MOD; // Strings ending in 'o' must be preceded by 'i' dp[i][3] = dp[i - 1][2]; // Strings ending in 'u' must be preceded by 'i' or 'o' dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % MOD; } long total = 0; for (int j = 0; j < 5; j++) { total = (total + dp[n][j]) % MOD; } return (int) total; }}Complexity
Time
O(n) - We iterate from 2 to `n`, and for each `i`, we perform a constant number of calculations (5 states).
Space
O(n) - We use a 2D DP table of size `(n+1) x 5`.
Trade-offs
Pros
Conceptually straightforward and directly translates the recurrence relations into code.
Efficient enough to pass the given constraints.
Cons
Uses linear space,
O(n), which is not optimal and can be a concern for very largen(though acceptable for the given constraints).
Observing the DP recurrence relations, we notice that to calculate the counts for strings of length i, we only need the counts from length i-1. This allows for a significant space optimization. Instead of storing the entire DP table, we only need to maintain the counts for the previous length, reducing the space complexity from linear to constant.
Algorithm
- Initialize five variables,
aCount,eCount,iCount,oCount,uCount, to 1, representing the counts for strings of length 1. - Iterate from
i = 2ton. - In each iteration, calculate the new counts for length
iinto temporary variables (aNew,eNew, etc.) using the same recurrence relations as the DP approach. - After calculating all five new counts, update the main count variables:
aCount = aNew,eCount = eNew, and so on. - After the loop, the total number of permutations is the sum of the final five count variables, modulo
10^9 + 7.
Walkthrough
This approach improves upon the standard DP by reducing space usage. We use a few variables to store the counts of strings ending in each vowel for the current length being processed. We iterate from length 2 up to n, and in each step, we compute the counts for the next length based on the current counts. This avoids storing a large n x 5 table, making the solution much more memory-efficient.
class Solution { public int countVowelPermutation(int n) { int MOD = 1_000_000_007; long aCount = 1, eCount = 1, iCount = 1, oCount = 1, uCount = 1; for (int i = 2; i <= n; i++) { long aCountNew = (eCount + iCount + uCount) % MOD; long eCountNew = (aCount + iCount) % MOD; long iCountNew = (eCount + oCount) % MOD; long oCountNew = iCount; long uCountNew = (iCount + oCount) % MOD; aCount = aCountNew; eCount = eCountNew; iCount = iCountNew; oCount = oCountNew; uCount = uCountNew; } long total = (aCount + eCount + iCount + oCount + uCount) % MOD; return (int) total; }}Complexity
Time
O(n) - The loop runs `n-1` times with a constant number of operations inside.
Space
O(1) - We only use a constant number of variables to store the counts, regardless of `n`.
Trade-offs
Pros
Extremely space-efficient, using only constant extra space.
Maintains a fast linear time complexity.
Simple to implement and understand.
Cons
While asymptotically optimal for the given constraints, it is slower than a logarithmic solution for extremely large
n.
For problems involving linear recurrences, a very powerful and asymptotically faster technique is matrix exponentiation. We can represent the state transitions (from strings of length i-1 to i) as a matrix multiplication. The number of strings of length n can then be found by raising this transition matrix to the power of n-1 and applying it to the initial state (strings of length 1).
Algorithm
- Define the 5x5 transition matrix
MwhereM[i][j] = 1if voweljcan be followed by voweli, and 0 otherwise. - The problem is to find the sum of elements in the vector
v_n = M^(n-1) * v_1, wherev_1is a vector of all ones[1,1,1,1,1]^T. - Implement a function for matrix multiplication of two 5x5 matrices, with all calculations done modulo
10^9 + 7. - Implement a function for matrix exponentiation (e.g., exponentiation by squaring) to compute
M_pow = M^(n-1)inO(log n)time. - The result
v_nisM_pow * v_1. Sincev_1is all ones, thei-th element ofv_nis just the sum of thei-th row ofM_pow. The total count is the sum of all elements inM_pow.
Walkthrough
The transition from the counts vector at length i-1 to the counts vector at length i can be expressed as v_i = M * v_{i-1}. By extension, v_n = M^(n-1) * v_1. The core of this approach is to compute M^(n-1) efficiently. We can do this using binary exponentiation (also known as exponentiation by squaring), which reduces the number of matrix multiplications from O(n) to O(log n). Each matrix multiplication takes O(k^3) time where k=5 is the number of vowels. This makes the overall time complexity logarithmic with respect to n.
class Solution { int MOD = 1_000_000_007; public int countVowelPermutation(int n) { if (n == 1) return 5; long[][] M = { {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} }; // Note: The matrix is transposed from the DP recurrence for easier multiplication with a column vector. // Let's use the one derived from the DP recurrence directly. long[][] transitionMatrix = { {0, 1, 1, 0, 1}, {1, 0, 1, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 1, 0} }; long[][] M_pow = matrixPower(transitionMatrix, n - 1); long total = 0; // The result is the sum of all entries in M_pow, as the initial vector is all 1s. for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { total = (total + M_pow[i][j]) % MOD; } } return (int) total; } private long[][] matrixMultiply(long[][] A, long[][] B) { long[][] C = new long[5][5]; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { for (int k = 0; k < 5; k++) { C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; } } } return C; } private long[][] matrixPower(long[][] A, int pow) { long[][] res = new long[5][5]; for (int i = 0; i < 5; i++) { res[i][i] = 1; // Identity matrix } long[][] P = A; while (pow > 0) { if ((pow & 1) == 1) { res = matrixMultiply(res, P); } P = matrixMultiply(P, P); pow >>= 1; } return res; }}Complexity
Time
O(log n) - The matrix size `k` is constant (5). Matrix multiplication is `O(k^3)` and binary exponentiation performs `O(log n)` multiplications. The total complexity is `O(k^3 * log n)`, which is `O(log n)`.
Space
O(1) - The space required for the matrices is `O(k^2)`, where `k=5` is a constant.
Trade-offs
Pros
Asymptotically the fastest approach with
O(log n)time complexity.Extremely efficient for very large values of
nthat would makeO(n)solutions too slow.
Cons
Significantly more complex to implement than the DP approaches.
The constant factor for the time complexity is larger, so for the given constraints (
n <= 2*10^4), it might not be practically faster than the O(n) solution.
Solutions
Solution
class Solution {public int countVowelPermutation(int n) { long[] f = new long[5]; Arrays.fill(f, 1); final int mod = (int)1 e9 + 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; }}/** * @param {number} n * @return {number} */ var countVowelPermutation = function ( n ) { const mod = 1 e9 + 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 ); }; 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) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.