Scale Engineer

Count Vowels Permutation

Hard
#1139Time: 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`.1 company
Patterns
Dynamic Programming
Companies
Atlassian

Prompt

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

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 large n (though acceptable for the given constraints).

Solutions

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

← Previous

Previous problem

Next →

Next problem