Count Vowels Permutation

HARD

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

Approaches

Checkout 3 different approaches to solve Count Vowels Permutation. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: O(n) - We iterate from 2 to `n`, and for each `i`, we perform a constant number of calculations (5 states).Space Complexity: O(n) - We use a 2D DP table of size `(n+1) x 5`.

Pros and Cons

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

Code Solutions

Checking out 4 solutions in different languages for Count Vowels Permutation. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Count Vowels Permutation

Patterns:

Dynamic Programming

Companies:

Atlassian |