# Count Vowels Permutation
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-vowels-permutation)
Canonical: https://scaleengineer.com/dsa/problems/count-vowels-permutation
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian)
---
## 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`.

**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
## Bottom-Up Dynamic Programming
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.
**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`.
**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 large `n` (though acceptable for the given constraints).
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
- Create a 2D array `dp` of size `(n + 1) x 5`, where `dp[i][j]` stores the number of valid strings of length `i` ending with the `j`-th vowel.
- **Base Case:** For strings of length 1, all vowels are possible. Initialize `dp[1][j] = 1` for all `j` from 0 to 4 (representing 'a' through 'u').
- **Recurrence Relation:** For `i` from 2 to `n`, calculate `dp[i][j]` based on the values in `dp[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]) % MOD`
  - `dp[i][e] = (dp[i-1][a] + dp[i-1][i]) % MOD`
  - `dp[i][i] = (dp[i-1][e] + dp[i-1][o]) % MOD`
  - `dp[i][o] = dp[i-1][i] % MOD`
  - `dp[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]`. Sum `dp[n][j]` for all `j` and take the final modulo.

## Space-Optimized Dynamic Programming
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.
**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`.
**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`.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize five variables, `aCount`, `eCount`, `iCount`, `oCount`, `uCount`, to 1, representing the counts for strings of length 1.
- Iterate from `i = 2` to `n`.
- In each iteration, calculate the new counts for length `i` into 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`.

## Matrix Exponentiation
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).
**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.
**Pros:** Asymptotically the fastest approach with `O(log n)` time complexity.; Extremely efficient for very large values of `n` that would make `O(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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
- Define the 5x5 transition matrix `M` where `M[i][j] = 1` if vowel `j` can be followed by vowel `i`, and 0 otherwise.
- The problem is to find the sum of elements in the vector `v_n = M^(n-1) * v_1`, where `v_1` is 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)` in `O(log n)` time.
- The result `v_n` is `M_pow * v_1`. Since `v_1` is all ones, the `i`-th element of `v_n` is just the sum of the `i`-th row of `M_pow`. The total count is the sum of all elements in `M_pow`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

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

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```