Jobs

Interviews

Discussions

Count Vowels Permutation

Hard

Asked by:

More companies

72 views

Topics:

Dynamic Programming

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

Try coding it in LeetCode

Count Vowels Permutation

Hard

Asked by:

72 views

Topics:

Dynamic Programming

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of `n` (the length of the vowel sequence)?
Is the value of `n` always a positive integer?
Should the result be returned modulo some number to prevent overflow? If so, what is the modulus?
Can you confirm that only lowercase vowels are allowed in the sequences?
If `n` is 0, should I return 0 or 1?

Brute Force Solution

Approach

The brute force way to solve this problem is to try out every single possible combination of vowels to form a string of the desired length. We'll generate all potential strings and count the ones that follow the allowed vowel sequences.

Here's how the algorithm would work step-by-step:

Start building strings one vowel at a time.
For the first vowel, consider all five possibilities: a, e, i, o, and u.
For each of these first vowels, try all the possible second vowels that are allowed to follow it, according to the rules. For example, if the first vowel is 'a', the next vowel must be 'e'.
Continue adding vowels to the string, one by one, always following the rules about which vowels can follow which.
Keep building the string until it reaches the required length.
Every time you successfully create a string of the correct length that follows all the rules, increase a counter.
After you've explored all possible combinations, the counter will hold the total number of valid strings, which is the answer.

Code Implementation

def count_vowel_permutation_brute_force(length):
    count = 0
    vowel_map = {
        'a': ['e'],
        'e': ['a', 'i'],
        'i': ['a', 'e', 'o', 'u'],
        'o': ['i', 'u'],
        'u': ['a']
    }

    def generate_strings(current_string):
        nonlocal count

        if len(current_string) == length:
            # String has the required length
            count += 1
            return

        last_vowel = current_string[-1] if current_string else None

        if not last_vowel:
            for vowel in 'aeiou':
                generate_strings(vowel)
        else:
            # Only proceed with valid sequence
            for next_vowel in vowel_map[last_vowel]:
                generate_strings(current_string + next_vowel)

    for vowel_start in 'aeiou':
        # Iterate through starting vowels
        generate_strings(vowel_start)

    return count % (10**9 + 7)

Big(O) Analysis

Time Complexity

O(5^n) – The described brute force approach explores all possible vowel sequences of length n. At each position in the string, there are up to 5 choices for the vowel. Since we are building strings of length n by considering all possible vowels at each position, the total number of possible strings we generate grows exponentially with n. Therefore, the algorithm explores approximately 5 * 5 * ... * 5 (n times) possible strings, resulting in a time complexity of O(5^n).

Space Complexity

O(N) – The described brute force approach uses recursion to build strings of length N. Each recursive call adds a new frame to the call stack. In the worst case, the depth of the recursion will be N, corresponding to the length of the string being built, as we add one vowel at a time. Therefore, the auxiliary space used by the recursion stack is proportional to N. This leads to a space complexity of O(N).

Optimal Solution

Approach

The key is to use a clever counting trick to avoid exploring every single vowel combination. We will keep track of counts of each vowel at each length, and build up these counts based on what vowels are allowed to follow which other vowels.

Here's how the algorithm would work step-by-step:

Recognize that the number of valid strings of length 'n' ending in a specific vowel only depends on the number of valid strings of length 'n-1'.
Maintain separate counters for each vowel ('a', 'e', 'i', 'o', 'u') at each step, representing how many valid strings of the current length can end with that vowel.
Start with the base case: when the length is 1, each vowel counter is initialized to 1 (because each vowel is a valid string of length 1).
Then, for each subsequent length, update the vowel counters based on the rules about which vowels can follow which. For instance, the number of strings ending in 'e' at length 'n' is equal to the number of strings ending in 'a' at length 'n-1'.
Continue updating these counters until you reach the target length 'n'.
Finally, add up all the vowel counters for length 'n'. The sum represents the total number of valid vowel permutations of length 'n'.

Code Implementation

def count_vowel_permutation(length):    modulo = 10**9 + 7
    a_count = 1
    e_count = 1
    i_count = 1
    o_count = 1
    u_count = 1

    if length == 1:
        return 5

    # Iterate to build up the counts for each length.
    for _ in range(2, length + 1):
        new_a_count = e_count + i_count + u_count
        new_e_count = a_count + i_count
        new_i_count = e_count + o_count
        new_o_count = i_count
        new_u_count = i_count + o_count

        a_count = new_a_count % modulo
        e_count = new_e_count % modulo
        i_count = new_i_count % modulo
        o_count = new_o_count % modulo
        u_count = new_u_count % modulo

    # Sum all vowel counts for the final length.
    return (a_count + e_count + i_count + o_count + u_count) % modulo

Big(O) Analysis

Time Complexity

O(n) – The dominant operation is the iteration to calculate vowel counts for each length from 2 up to n. Inside the loop, we perform a constant number of operations (updating the vowel counters based on the rules). Since this loop runs 'n-1' times, the overall time complexity is proportional to n, resulting in O(n).

Space Complexity

O(1) – The solution maintains a fixed number of counters, one for each vowel ('a', 'e', 'i', 'o', 'u'), at each length calculation. Since the number of vowels is constant (5), the memory required to store these counters does not depend on the input length N. Therefore, the auxiliary space used remains constant regardless of the value of N, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
n = 0	Return 0 since no permutation is possible with length zero.
n = 1	Return 5, as any of the five vowels is a valid permutation.
Large value of n (e.g., close to the constraint limit)	Use dynamic programming with memoization to avoid redundant calculations and integer overflow by using modulo arithmetic.
Integer overflow when calculating the number of permutations	Apply modulo operation during each calculation step to prevent integer overflow.
Invalid input (n < 0)	Throw an IllegalArgumentException or return 0, indicating invalid input.
No valid solutions exist (edge case impossible for this problem)	This scenario is inherently impossible given the problem definition, so no specific handling is needed.
All vowels can start, skew is not an issue	The iterative nature of the dynamic programming solution inherently handles the balanced distribution of vowels.
Modulo value is prime or not. (Modulo arithmetic specifics)	The problem specifies a prime modulo, ensuring basic operations will work without special considerations for inverses.

n = 0

How to Handle:

Return 0 since no permutation is possible with length zero.

n = 1

How to Handle:

Return 5, as any of the five vowels is a valid permutation.

Large value of n (e.g., close to the constraint limit)

How to Handle:

Use dynamic programming with memoization to avoid redundant calculations and integer overflow by using modulo arithmetic.

Integer overflow when calculating the number of permutations

How to Handle:

Apply modulo operation during each calculation step to prevent integer overflow.

Invalid input (n < 0)

How to Handle:

Throw an IllegalArgumentException or return 0, indicating invalid input.

No valid solutions exist (edge case impossible for this problem)

How to Handle:

This scenario is inherently impossible given the problem definition, so no specific handling is needed.

All vowels can start, skew is not an issue

How to Handle:

The iterative nature of the dynamic programming solution inherently handles the balanced distribution of vowels.

Modulo value is prime or not. (Modulo arithmetic specifics)

How to Handle:

The problem specifies a prime modulo, ensuring basic operations will work without special considerations for inverses.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of `n` (the length of the vowel sequence)?
Is the value of `n` always a positive integer?
Should the result be returned modulo some number to prevent overflow? If so, what is the modulus?
Can you confirm that only lowercase vowels are allowed in the sequences?
If `n` is 0, should I return 0 or 1?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start building strings one vowel at a time.
For the first vowel, consider all five possibilities: a, e, i, o, and u.
For each of these first vowels, try all the possible second vowels that are allowed to follow it, according to the rules. For example, if the first vowel is 'a', the next vowel must be 'e'.
Continue adding vowels to the string, one by one, always following the rules about which vowels can follow which.
Keep building the string until it reaches the required length.
Every time you successfully create a string of the correct length that follows all the rules, increase a counter.
After you've explored all possible combinations, the counter will hold the total number of valid strings, which is the answer.

Code Implementation

def count_vowel_permutation_brute_force(length):
    count = 0
    vowel_map = {
        'a': ['e'],
        'e': ['a', 'i'],
        'i': ['a', 'e', 'o', 'u'],
        'o': ['i', 'u'],
        'u': ['a']
    }

    def generate_strings(current_string):
        nonlocal count

        if len(current_string) == length:
            # String has the required length
            count += 1
            return

        last_vowel = current_string[-1] if current_string else None

        if not last_vowel:
            for vowel in 'aeiou':
                generate_strings(vowel)
        else:
            # Only proceed with valid sequence
            for next_vowel in vowel_map[last_vowel]:
                generate_strings(current_string + next_vowel)

    for vowel_start in 'aeiou':
        # Iterate through starting vowels
        generate_strings(vowel_start)

    return count % (10**9 + 7)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Recognize that the number of valid strings of length 'n' ending in a specific vowel only depends on the number of valid strings of length 'n-1'.
Maintain separate counters for each vowel ('a', 'e', 'i', 'o', 'u') at each step, representing how many valid strings of the current length can end with that vowel.
Start with the base case: when the length is 1, each vowel counter is initialized to 1 (because each vowel is a valid string of length 1).
Then, for each subsequent length, update the vowel counters based on the rules about which vowels can follow which. For instance, the number of strings ending in 'e' at length 'n' is equal to the number of strings ending in 'a' at length 'n-1'.
Continue updating these counters until you reach the target length 'n'.
Finally, add up all the vowel counters for length 'n'. The sum represents the total number of valid vowel permutations of length 'n'.

Code Implementation

def count_vowel_permutation(length):    modulo = 10**9 + 7
    a_count = 1
    e_count = 1
    i_count = 1
    o_count = 1
    u_count = 1

    if length == 1:
        return 5

    # Iterate to build up the counts for each length.
    for _ in range(2, length + 1):
        new_a_count = e_count + i_count + u_count
        new_e_count = a_count + i_count
        new_i_count = e_count + o_count
        new_o_count = i_count
        new_u_count = i_count + o_count

        a_count = new_a_count % modulo
        e_count = new_e_count % modulo
        i_count = new_i_count % modulo
        o_count = new_o_count % modulo
        u_count = new_u_count % modulo

    # Sum all vowel counts for the final length.
    return (a_count + e_count + i_count + o_count + u_count) % modulo

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Return 0 since no permutation is possible with length zero.
n = 1	Return 5, as any of the five vowels is a valid permutation.
Large value of n (e.g., close to the constraint limit)	Use dynamic programming with memoization to avoid redundant calculations and integer overflow by using modulo arithmetic.
Integer overflow when calculating the number of permutations	Apply modulo operation during each calculation step to prevent integer overflow.
Invalid input (n < 0)	Throw an IllegalArgumentException or return 0, indicating invalid input.
No valid solutions exist (edge case impossible for this problem)	This scenario is inherently impossible given the problem definition, so no specific handling is needed.
All vowels can start, skew is not an issue	The iterative nature of the dynamic programming solution inherently handles the balanced distribution of vowels.
Modulo value is prime or not. (Modulo arithmetic specifics)	The problem specifies a prime modulo, ensuring basic operations will work without special considerations for inverses.

n = 0

How to Handle:

Return 0 since no permutation is possible with length zero.

n = 1

How to Handle:

Return 5, as any of the five vowels is a valid permutation.

Large value of n (e.g., close to the constraint limit)

How to Handle:

Use dynamic programming with memoization to avoid redundant calculations and integer overflow by using modulo arithmetic.

Integer overflow when calculating the number of permutations

How to Handle:

Apply modulo operation during each calculation step to prevent integer overflow.

Invalid input (n < 0)

How to Handle:

Throw an IllegalArgumentException or return 0, indicating invalid input.

No valid solutions exist (edge case impossible for this problem)

How to Handle:

This scenario is inherently impossible given the problem definition, so no specific handling is needed.

All vowels can start, skew is not an issue

How to Handle:

The iterative nature of the dynamic programming solution inherently handles the balanced distribution of vowels.

Modulo value is prime or not. (Modulo arithmetic specifics)

How to Handle:

The problem specifies a prime modulo, ensuring basic operations will work without special considerations for inverses.