Count Vowels Permutation
Hard · 1-D Dynamic Programming · Explanation and code example
Matrix Exponentiation
How it works
The transition between states can be represented as a matrix multiplication. If we define a transition matrix T where T[i][j] = 1 if vowel j can follow vowel i, then multiplying the state vector by T gives the next state. To get the state after n-1 transitions, we compute T^(n-1). Matrix exponentiation allows us to compute this in O(log n) time instead of O(n).
Steps
- Define the 5x5 transition matrix based on the vowel succession rules.
- Implement matrix multiplication for 5x5 matrices.
- Implement matrix exponentiation using binary exponentiation.
- Compute
T^(n-1)whereTis the transition matrix. - The result is the sum of all elements in the resulting matrix (since we start with
1of each vowel). - Return the result modulo
10^9 + 7.
Complexity
- Time complexity:
O(m ^ 3 log n) - Space complexity:
O(m ^ 2)
Where
mis the size of the matrix used in matrix exponentiation(5 X 5)andnis the length of the permutation.
Things to watch for
Confusing "Follows" vs "Precedes" Transitions
The problem states which vowels can follow each vowel, but the DP recurrence requires knowing which vowels can precede each vowel. Mixing up the direction leads to wrong transition rules.
Forgetting Modulo in Intermediate Sums
With large n, intermediate sums overflow before taking the final modulo. Apply modulo after each addition to keep values within bounds.
Incorrect Matrix Exponentiation Base Case
When using matrix exponentiation, computing T^n instead of T^(n-1) is a common error. The initial state already represents strings of length 1, so only n-1 transitions are needed.
Not Handling n=1 Edge Case
For n=1, the answer is simply 5 (one for each vowel). Some implementations with matrix exponentiation or DP loops may fail if they do not handle this boundary correctly.
Integer Overflow in Matrix Multiplication
In languages without arbitrary precision integers (like Java, C++), multiplying two large values before taking modulo causes overflow. Cast to a larger type or restructure the multiplication.
Python code example
from itertools import product
class Solution:
MOD = 10**9 + 7
class M:
def __init__(self, n):
self.a = [[0] * n for _ in range(n)]
def __mul__(self, other):
n = len(self.a)
product = Solution.M(n)
for i in range(n):
for j in range(n):
for k in range(n):
product.a[i][k] = (product.a[i][k] + self.a[i][j] * other.a[j][k]) % Solution.MOD
return product
def matrixExpo(self, base, exp):
n = len(base.a)
result = Solution.M(n)
for i in range(n):
result.a[i][i] = 1
while exp > 0:
if exp % 2 == 1:
result = result * base
base = base * base
exp //= 2
return result
def countVowelPermutation(self, n: int) -> int:
follows = [
[0, 1, 0, 0, 0], # 'a' -> 'e'
[1, 0, 1, 0, 0], # 'e' -> 'a', 'i'
[1, 1, 0, 1, 1], # 'i' -> 'a', 'e', 'o', 'u'
[0, 0, 1, 0, 1], # 'o' -> 'i', 'u'
[1, 0, 0, 0, 0] # 'u' -> 'a'
]
base = Solution.M(5)
base.a = follows
result = self.matrixExpo(base, n - 1)
return sum(sum(row) for row in result.a) % self.MOD
C++ code example
class Solution {
static const int MOD = 1e9 + 7;
struct M {
vector<vector<int>> a;
M(int n) {
a.resize(n, vector<int>(n, 0));
}
M operator*(const M& other) const {
int n = a.size();
M product(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
product.a[i][k] = (product.a[i][k] + a[i][j] * 1LL * other.a[j][k]) % MOD;
}
}
}
return product;
}
};
M matrixExpo(M base, int exp) {
int n = base.a.size();
M result(n);
for (int i = 0; i < n; i++) {
result.a[i][i] = 1;
}
while (exp > 0) {
if (exp % 2 == 1) {
result = result * base;
}
base = base * base;
exp /= 2;
}
return result;
}
public:
int countVowelPermutation(int n) {
vector<vector<int>> follows = {
{0, 1, 0, 0, 0}, // 'a' -> 'e'
{1, 0, 1, 0, 0}, // 'e' -> 'a', 'i'
{1, 1, 0, 1, 1}, // 'i' -> 'a', 'e', 'o', 'u'
{0, 0, 1, 0, 1}, // 'o' -> 'i', 'u'
{1, 0, 0, 0, 0} // 'u' -> 'a'
};
M base(5);
base.a = follows;
M result = matrixExpo(base, n - 1);
int ans = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
ans = (ans + result.a[i][j]) % MOD;
}
}
return ans;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.