Count Vowels Permutation Leetcode Problem 1220 [Python Solution]

In this blog post, we will tackle the Count Vowels Permutation problem, a challenging LeetCode problem categorized under 2-D Dynamic Programming.

We’ll provide a detailed explanation of the problem, discuss constraints, explore a brute-force approach with Python code, and finally, present an efficient approach along with reasoning.

Let’s dive in!

Problem Overview

Question: 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 lowercase 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

Now, let’s proceed to understand the problem constraints in more detail.

Understanding Constraints

The constraints provide us with the boundaries within which our solution must work efficiently.

For this problem, we have the following constraints:

n is an integer that represents the length of the strings we need to generate.
n can range from 1 to 20,000, which implies that our solution should be efficient enough to handle a significant range of input values without causing performance issues.

We need to ensure that our solution remains within these constraints as we design and implement it.

Count Vowels Permutation LeetCode Problem Solution

Bruteforce Approach

Before diving into the efficient approach, let’s explore a more straightforward, brute-force solution to get a better understanding of the problem.

We’ll use Python for this demonstration.

Memo = {}

def countVowelPermutation(self, n, c = '') -> int:
    if (c, n) in self.Memo:
        return self.Memo[(c, n)]
    if n == 1:
        if c == 'a':
            return 1 
        if c == 'e':
            return 2 
        if c == 'i':
            return 4 
        if c == 'o':
            return 2 
        if c == 'u':
            return 1            
        if c == '':
            return 5
    else:
        if c == 'a':
            self.Memo[('a', n)] = self.countVowelPermutation(n - 1, 'e')                
            return self.Memo[('a', n)]
        if c == 'e':
            self.Memo[('e', n)] = self.countVowelPermutation(n - 1, 'a') + self.countVowelPermutation(n - 1, 'i')                
            return self.Memo[('e', n)]
        if c == 'i':
            self.Memo[('i', n)] = self.countVowelPermutation(n - 1, 'a') + self.countVowelPermutation(n - 1, 'e') + self.countVowelPermutation(n - 1, 'o') + self.countVowelPermutation(n - 1, 'u')          
            return self.Memo[('i', n)]
        if c == 'o':
            self.Memo[('o', n)] = self.countVowelPermutation(n - 1, 'i') + self.countVowelPermutation(n - 1, 'u')                
            return self.Memo[('o', n)]
        if c == 'u':
            self.Memo[('u', n)] = self.countVowelPermutation(n - 1, 'a')                
            return self.Memo[('u', n)]
        if c == '':
            Tot = 0
            for i in ['a', 'e', 'i', 'o', 'u']:
                Tot = Tot + self.countVowelPermutation(n - 1, i)                    
            return Tot % 1000000007

This brute-force approach involves recursion and memoization.

We calculate the number of strings of length n that can be formed based on the given rules.

While this approach works, it can become inefficient for large values of n.

2. Efficient Approach

Now, let’s dive into a more efficient approach to solving the problem.

We will use dynamic programming to optimize the solution.

Dynamic Programming Explanation

We will use a two-dimensional array to store the count of valid strings for each length n and ending with each vowel (‘a’, ‘e’, ‘i’, ‘o’, ‘u’).

This array will be referred to as dp.

The first dimension of the array represents the length of the string, and the second dimension represents the last character of the string.

We will initialize dp with values corresponding to strings of length 1. To fill in the values for dp for strings of length n, we will use the following logic:

For each vowel, we will calculate the number of strings of length n ending with that vowel.
We will use the rules provided in the problem to determine which vowels can follow the current vowel.
We will calculate the total count for the current vowel based on the counts of valid strings for the preceding vowels that can be followed by the current vowel.

Let’s look at the dynamic programming code to implement this approach:

View on GitHub ➹

def countVowelPermutation(self, n: int) -&gt; int:
    MOD = 10**9 + 7

    # Initialize dp with values for strings of length 1
    dp = [[0] * 5 for _ in range(n)]
    for i in range(5):
        dp[0][i] = 1

    # Fill in the dp array for strings of length 2 to n
    for length in range(1, n):
        dp[length][0] = (dp[length - 1][1] + dp[length - 1][2] + dp[length - 1][4]) % MOD
        dp[length][1] = (dp[length - 1][0] + dp[length - 1][2]) % MOD
        dp[length][2] = (dp[length - 1][1] + dp[length - 1][3]) % MOD
        dp[length][3] = (dp[length - 1][2]) % MOD
        dp[length][4] = (dp[length - 1][

2] + dp[length - 1][3]) % MOD

    # Calculate the total count for strings of length n
    total_count = sum(dp[n - 1]) % MOD

    return total_count

In this efficient approach, we calculate the count of valid strings of length n while adhering to the specified rules.

The dynamic programming table dp allows us to store intermediate results and avoid redundant calculations.

Time and Space Complexity

Time Complexity: The time complexity of the efficient approach is O(n), where n is the length of the input.

We only iterate through the length of the string once to calculate the counts for all valid strings.

Space Complexity: The space complexity is O(1) since the size of the dynamic programming table is fixed and does not depend on the input size.

Reasoning Behind Our Approach

The efficient approach we discussed is based on dynamic programming, which allows us to avoid redundant calculations and optimize the solution.

We start with the base case for strings of length 1 and build our way up to strings of length n.

By considering the rules and dependencies between vowels, we can calculate the counts efficiently.

Conclusion

In this blog post, we addressed the Count Vowels Permutation problem from LeetCode.

We provided a detailed explanation of the problem, explored its constraints, and presented both a brute-force approach and an efficient dynamic programming approach with Python code.

Optimizing the solution using dynamic programming allows us to handle larger input values efficiently.

We hope this explanation and solution help you understand and tackle similar problems.

If you have any questions, suggestions, or feedback, please feel free to comment and share your thoughts.

Happy coding!

Question Link: Count Vowels Permutation on LeetCode

Remember, practice is key to mastering algorithmic problem-solving, and LeetCode offers a great platform to hone your skills.

Keep coding and learning!