NeetCode #740LC-1220Hard2-D Dynamic Programming
← Back to All Problems#740 · #1220 · Count Vowels Permutation(统计元音字母序列的数目)
📌 Problem Statement & Constraints
Count the number of strings of length
n over the vowels a, e, i, o, u such that each character is followed only by allowed letters: a to e; e to a or i; i to a, e, o, u; o to i or u; u to a. Return the count modulo 1e9+7. Constraints: 1 <= n <= 2 * 10^4.💡 Core Algorithmic Approaches
- Track the number of valid strings ending in each vowel, since only the last character constrains the next one.
- Reading the transition graph backwards: a string ending in
emay have been extended fromaori, sonew[e] = a + i. - Apply the analogous rule for each vowel and repeat
n - 1times; all five vowels start at 1 for length 1. - The answer is the sum of the five counters after the final transition.
💻 Benchmark Python3 Implementation
class Solution:
def countVowelPermutation(self, n: int) -> int:
MOD = 10**9 + 7
a = e = i = o = u = 1 # every single vowel is a valid length-1 string
for _ in range(n - 1):
a, e, i, o, u = (
(e + i + u) % MOD, # a can be preceded by e, i, u
(a + i) % MOD, # e can be preceded by a, i
(e + o) % MOD, # i can be preceded by e, o
(i + u) % MOD, # o can be preceded by i, u
i % MOD, # u can be preceded only by i
)
return (a + e + i + o + u) % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one constant-time transition per length.
💾 Space Complexity
O(1): five counters.
⚠️ Interview Pitfalls & Follow-ups
- Reversing the transition direction:
a -> emeans a string ending inemay be preceded bya, sonew[e]gains froma; mixing the two directions gives wrong counts. - Using a full
n x 5table: only the previous length is needed, so five scalars suffice. - Forgetting the modulo: counts grow exponentially and overflow quickly for
nup to 2 * 10^4. - Initialising the base case to 0: every single vowel is a valid length-1 string, so all five start at 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.