We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Vowels Permutation

Number: 1332

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given an integer n, count the number of strings of length n that can be formed using only lowercase vowels ('a', 'e', 'i', 'o', 'u') under the following transition rules:

  • 'a' may only be followed by 'e'.
  • 'e' may only be followed by 'a' or 'i'.
  • 'i' may not be followed by another 'i' (but can be followed by any other vowel).
  • 'o' may only be followed by 'i' or 'u'.
  • 'u' may only be followed by 'a'. Return the count of such strings modulo 10^9 + 7.

Key Insights

  • Use dynamic programming to count valid strings ending with each vowel.
  • Transitions are based on the allowed following vowels:
    • a -> e
    • e -> a, i
    • i -> a, e, o, u (excluding i)
    • o -> i, u
    • u -> a
  • Instead of moving forward using these rules, we reverse the thinking:
    • For each vowel ending, determine which vowels from the previous step could have transitioned to it.
  • Only a constant amount of memory is needed to track counts for each vowel, leading to an O(1) space solution.
  • The iterative process runs in O(n) time.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), since only five counters for the vowels are maintained.

Solution

We use a dynamic programming approach that maintains counts for strings ending with each vowel at each length. Let:

  • count_a, count_e, count_i, count_o, count_u be the current counts for strings ending with 'a', 'e', 'i', 'o', and 'u', respectively. For n = 1, each vowel has a count of 1. For each subsequent position (from 2 to n), we update the counts based on reverse allowed transitions:
  • New count for 'a' = (previous count for 'e' + previous count for 'i' + previous count for 'u') because 'a' can follow e, i, or u.
  • New count for 'e' = (previous count for 'a' + previous count for 'i') because 'e' can follow a or i.
  • New count for 'i' = (previous count for 'e' + previous count for 'o') because 'i' can follow e or o (note: i cannot follow itself).
  • New count for 'o' = (previous count for 'i') because 'o' can only follow i.
  • New count for 'u' = (previous count for 'i' + previous count for 'o') because 'u' can follow i or o. After updating for all positions, the answer is the sum of counts for all vowels modulo 10^9+7.

Code Solutions

# Python solution for Count Vowels Permutation
MOD = 10**9 + 7

def countVowelPermutation(n: int) -> int:
    # Initialize counts for each vowel at length 1
    count_a = count_e = count_i = count_o = count_u = 1
    
    # Iterate to build strings of increasing length
    for _ in range(2, n + 1):
        # Calculate new counts based on allowed transitions:
        next_a = (count_e + count_i + count_u) % MOD    # 'a' can come from e, i, u
        next_e = (count_a + count_i) % MOD                # 'e' can come from a, i
        next_i = (count_e + count_o) % MOD                # 'i' can come from e, o
        next_o = count_i % MOD                            # 'o' can come from i
        next_u = (count_i + count_o) % MOD                # 'u' can come from i, o
        
        # Update the counts for the next iteration
        count_a, count_e, count_i, count_o, count_u = next_a, next_e, next_i, next_o, next_u
    
    # Sum up counts for all vowels to obtain the final result modulo MOD
    return (count_a + count_e + count_i + count_o + count_u) % MOD

# Example usage:
# print(countVowelPermutation(5))
← Back to All Questions