hard Count Vowels Permutation

Problem Statement

Given a positive integer n, return the number of strings of length n can be formed by following rules:

• Each character of the string should be only a lowercase vowel ('a', 'e', 'i', 'o', 'u').
• The vowel 'a' is only allowed to be followed by the vowel 'e'.
• The vowel 'e' can be followed by either 'a' or 'i'.
• The vowel 'i' cannot be followed by another 'i'.
• The vowel 'o' can be followed by either 'i' or 'u'.
• The vowel 'u' must be followed by 'a'.

Return the answer modulo 10^9 + 7, as it could be very large.

Examples

Example 1:

• Input: n = 1
• Expected Output: 5
• Justification: There's only one position, and each vowel can occupy it without restrictions, resulting in 5 possible strings: 'a', 'e', 'i', 'o', 'u'.

Example 2:

• Input: n = 2
• Expected Output: 10
• Justification: Two-character strings following the rules give us ten possibilities: 'ae', 'ea', 'ei', 'ia', 'ie', 'io', 'iu', 'oi', 'ou', 'ua'.

Example 3:

• Input: n = 4
• Expected Output: 35
• Justification: For strings of length 4, following the succession rules strictly, there are 35 valid combinations.

Solution

To solve this problem, we adopt a dynamic programming approach, as it allows us to efficiently compute the total number of valid strings by reusing the results of smaller sub-problems. This problem exhibits both optimal substructure and overlapping subproblems, making dynamic programming an ideal solution. We'll maintain a table where each cell represents the number of strings of length n ending with a specific vowel. By iteratively updating this table for lengths from 1 to n, we ensure that all possible strings are accounted for, following the given rules for vowel succession.

This approach is effective because it builds the solution incrementally, avoiding the redundancy of recalculating the number of strings for smaller lengths. By only considering the last vowel in a string of length n-1 to add the next vowel according to the rules, we can efficiently calculate the number of valid strings of any length. This method not only guarantees that all rules are followed but also significantly reduces the computational complexity compared to a naive approach that might attempt to generate all possible strings and filter them post-hoc.

Step-by-step Algorithm

• Initialize a 2D array dp with dimensions 5 x n, where each row represents one of the vowels in the order 'a', 'e', 'i', 'o', 'u', and each column represents the string length from 1 to n.
• Set the first column of dp to 1, since there's exactly one string of length 1 for each vowel.
• For each column (string length) from 2 to n, update dp based on the succession rules:
  • dp[a][i] = dp[e][i-1] + dp[i][i-1] + dp[u][i-1] (since 'a' can follow 'e', 'i', 'u')
  • dp[e][i] = dp[a][i-1] + dp[i][i-1] (since 'e' can follow 'a', 'i')
  • dp[i][i] = dp[e][i-1] + dp[o][i-1] (since 'i' can follow 'e', 'o')
  • dp[o][i] = dp[i][i-1] (since 'o' can follow 'i')
  • dp[u][i] = dp[i][i-1] + dp[o][i-1] (since 'u' can follow 'i', 'o')
• Sum the final column of dp to get the total number of strings of length n.
• Return the sum modulo (10^9 + 7) as the final result.

Algorithm Walkthrough

Let's consider the Input: n = 4.

Initial Setup

• Initialize a 2D array dp where each row represents a vowel ('a', 'e', 'i', 'o', 'u') and columns represent string lengths (1 to 4).
• For length 1 (n = 1), all vowels ('a', 'e', 'i', 'o', 'u') have 1 possibility each.

Calculations for Each Length

For Length 2 (n = 2)

1. Calculating for 'a': dp[a][2] = dp[e][1] + dp[i][1] + dp[u][1] = 1 + 1 + 1 = 3
2. Calculating for 'e': dp[e][2] = dp[a][1] + dp[i][1] = 1 + 1 = 2
3. Calculating for 'i': dp[i][2] = dp[e][1] + dp[o][1] = 1 + 1 = 2
4. Calculating for 'o': dp[o][2] = dp[i][1] = 1
5. Calculating for 'u': dp[u][2] = dp[i][1] + dp[o][1] = 1 + 1 = 2

Updated counts: a: 3, e: 2, i: 2, o: 1, u: 2

For Length 3 (n = 3)

1. Calculating for 'a': dp[a][3] = dp[e][2] + dp[i][2] + dp[u][2] = 2 + 2 + 2 = 6
2. Calculating for 'e': dp[e][3] = dp[a][2] + dp[i][2] = 3 + 2 = 5
3. Calculating for 'i': dp[i][3] = dp[e][2] + dp[o][2] = 2 + 1 = 3
4. Calculating for 'o': dp[o][3] = dp[i][2] = 2
5. Calculating for 'u': dp[u][3] = dp[i][2] + dp[o][2] = 2 + 1 = 3

Updated counts: a: 6, e: 5, i: 3, o: 2, u: 3

For Length 4 (n = 4)

1. Calculating for 'a': dp[a][4] = dp[e][3] + dp[i][3] + dp[u][3] = 5 + 3 + 3 = 11
2. Calculating for 'e': dp[e][4] = dp[a][3] + dp[i][3] = 6 + 3 = 9
3. Calculating for 'i': dp[i][4] = dp[e][3] + dp[o][3] = 5 + 2 = 7
4. Calculating for 'o': dp[o][4] = dp[i][3] = 3
5. Calculating for 'u': dp[u][4] = dp[i][3] + dp[o][3] = 3 + 2 = 5

Updated counts: a: 11, e: 9, i: 7, o: 3, u: 5

Final Summation for n = 4

• Sum the counts of strings of length 4 ending with each vowel: 11 (a) + 9 (e) + 7 (i) + 3 (o) + 5 (u) = 35

Code

public class Solution {

  private static final int MOD = 1000000007;

  public int countVowelPermutation(int n) {
    long[][] dp = new long[5][n + 1];
    // Initialize dp array for n = 1
    for (int i = 0; i < 5; i++) dp[i][1] = 1;

    // Update dp values based on rules
    for (int i = 2; i <= n; i++) {
      dp[0][i] = (dp[1][i - 1] + dp[2][i - 1] + dp[4][i - 1]) % MOD; // a follows e, i, u
      dp[1][i] = (dp[0][i - 1] + dp[2][i - 1]) % MOD; // e follows a, i
      dp[2][i] = (dp[1][i - 1] + dp[3][i - 1]) % MOD; // i follows e, o
      dp[3][i] = dp[2][i - 1] % MOD; // o follows i
      dp[4][i] = (dp[2][i - 1] + dp[3][i - 1]) % MOD; // u follows i, o
    }

    // Sum up the last column for total count
    long result = 0;
    for (int i = 0; i < 5; i++) result = (result + dp[i][n]) % MOD;

    return (int) result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.countVowelPermutation(1)); // 5
    System.out.println(solution.countVowelPermutation(2)); // 10
    System.out.println(solution.countVowelPermutation(4)); // 35
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where (n) is the length of the string to be formed. This is because the algorithm iterates through each length from 1 to (n), updating the count of strings ending with each vowel according to the predefined rules. The updates at each step involve only a constant number of operations (additions and modulo operations), making the time complexity linear with respect to the input length (n).

Space Complexity

The space complexity of the algorithm is , as it maintains a 2-dimensional array of size 5 * (n+1) to store the counts of strings of length up to (n) ending with each vowel. The "5" here is constant (since there are five vowels), so the space complexity is essentially linear with respect to the length of the string (n).