Count Vowels Permutation

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

Key Insights

• This is a dynamic programming problem where we can maintain a count of valid permutations ending with each vowel.
• The transitions between the vowels are defined by the problem constraints.
• The solution can be built up iteratively from smaller values of n to n.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use dynamic programming to count the number of valid strings of length n that can be formed ending with each vowel. We maintain a count for each vowel and update these counts based on the allowed transitions:

1. Initialize an array to hold the counts for each vowel.
2. For each length from 1 to n, update the counts based on the rules defined.
3. Sum the counts for all vowels at the end to get the total number of valid strings.

The algorithm proceeds iteratively, ensuring that we only store the counts needed for the current computation, leading to a space complexity of O(1).

Code Solutions