⚡Flashcard Drill➔
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

  1. Track the number of valid strings ending in each vowel, since only the last character constrains the next one.
  2. Reading the transition graph backwards: a string ending in e may have been extended from a or i, so new[e] = a + i.
  3. Apply the analogous rule for each vowel and repeat n - 1 times; all five vowels start at 1 for length 1.
  4. 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 -> e means a string ending in e may be preceded by a, so new[e] gains from a; mixing the two directions gives wrong counts.
  • Using a full n x 5 table: only the previous length is needed, so five scalars suffice.
  • Forgetting the modulo: counts grow exponentially and overflow quickly for n up 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems