Count Vowels Permutation

Count Vowels Permutation

What is this problem about?

The Count Vowels Permutation interview question asks you to find the number of valid strings of length n that can be formed using the vowels 'a', 'e', 'i', 'o', and 'u' following specific transition rules:

• 'a' can only be followed by 'e'.
• 'e' can only be followed by 'a' or 'i'.
• 'i' cannot be followed by another 'i'.
• 'o' can only be followed by 'i' or 'u'.
• 'u' can only be followed by 'a'. You need to return the total number of such strings modulo $10^9 + 7$.

Why is this asked in interviews?

Atlassian and other tech companies use this Dynamic Programming coding problem to see if a candidate can model a state machine using DP. It tests your ability to handle state transitions and optimize space. Since each character's possibility depends only on the previous character, this is a classic "linear DP" problem.

Algorithmic pattern used

The problem uses Dynamic Programming with state compression.

1. Let dp[i][v] be the number of valid strings of length i ending with vowel v.
2. The state at i depends only on the counts at i-1. For example, a string of length i ends in 'e' if the string of length i-1 ended in 'a' or 'i'.
3. The recurrence relations are:
   • next_a = e + i + u
   • next_e = a + i
   • next_i = e + o
   • next_o = i
   • next_u = i + o
4. Since we only need the previous step, we can use 5 variables instead of a 2D array, reducing space complexity to O(1).

Example explanation

n = 1: All 5 vowels are valid. Total = 5. n = 2:

• Ending in 'a': previous could be 'e', 'i', 'u'. (3 ways)
• Ending in 'e': previous could be 'a', 'i'. (2 ways)
• Ending in 'i': previous could be 'e', 'o'. (2 ways)
• Ending in 'o': previous could be 'i'. (1 way)
• Ending in 'u': previous could be 'i', 'o'. (2 ways) Total = 3 + 2 + 2 + 1 + 2 = 10.

Common mistakes candidates make

• Integer Overflow: Not applying the modulo $10^9 + 7$ at each addition step.
• Incorrect Transitions: Misinterpreting the "followed by" rules. It's often easier to think about which vowels can precede the current vowel.
• Complexity: Trying to use recursion without memoization, leading to exponential time complexity.

Interview preparation tip

This problem is essentially a directed graph where you are counting paths of length n. For very large n, you could even solve this using Matrix Exponentiation in O(log n) time.