Count Vowels Permutation

hard dp modular arithmetic

Problem

Count strings of length n made of vowels (a, e, i, o, u) following these rules: 'a' may be followed only by 'e'; 'e' may be followed by 'a' or 'i'; 'i' may not be followed by another 'i'; 'o' may be followed by 'i' or 'u'; 'u' may be followed only by 'a'. Return the count modulo 10^9 + 7.

Inputn = 2

Output10

Valid pairs: ae, ea, ei, ia, ie, io, iu, oi, ou, ua.

def count_vowel_permutation(n):
    MOD = 10**9 + 7
    a, e, i, o, u = 1, 1, 1, 1, 1
    for _ in range(n - 1):
        a, e, i, o, u = (
            (e + i + u) % MOD,
            (a + i) % MOD,
            (e + o) % MOD,
            i % MOD,
            (i + o) % MOD,
        )
    return (a + e + i + o + u) % MOD

function countVowelPermutation(n) {
  const MOD = 1000000007n;
  let a = 1n, e = 1n, i = 1n, o = 1n, u = 1n;
  for (let k = 1; k < n; k++) {
    [a, e, i, o, u] = [
      (e + i + u) % MOD,
      (a + i) % MOD,
      (e + o) % MOD,
      i % MOD,
      (i + o) % MOD,
    ];
  }
  return Number((a + e + i + o + u) % MOD);
}

class Solution {
    public int countVowelPermutation(int n) {
        long MOD = 1_000_000_007L;
        long a = 1, e = 1, i = 1, o = 1, u = 1;
        for (int k = 1; k < n; k++) {
            long na = (e + i + u) % MOD;
            long ne = (a + i) % MOD;
            long ni = (e + o) % MOD;
            long no = i % MOD;
            long nu = (i + o) % MOD;
            a = na; e = ne; i = ni; o = no; u = nu;
        }
        return (int)((a + e + i + o + u) % MOD);
    }
}

int countVowelPermutation(int n) {
    const long long MOD = 1000000007LL;
    long long a = 1, e = 1, i = 1, o = 1, u = 1;
    for (int k = 1; k < n; k++) {
        long long na = (e + i + u) % MOD;
        long long ne = (a + i) % MOD;
        long long ni = (e + o) % MOD;
        long long no = i % MOD;
        long long nu = (i + o) % MOD;
        a = na; e = ne; i = ni; o = no; u = nu;
    }
    return (int)((a + e + i + o + u) % MOD);
}

Explanation

We count valid vowel strings by tracking, for each length, how many strings end in each vowel. Since the rules only care about the last letter, knowing those five counts is enough to extend to the next length.

We start at length 1 with a = e = i = o = u = 1: each vowel alone is one valid string.

To grow by one letter, we ask "which vowels can come before each vowel?" From the rules: an a can be preceded by e, i, u; an e by a, i; an i by e, o; an o by i; and a u by i, o. So the new counts are a = e + i + u, e = a + i, i = e + o, o = i, u = i + o, each taken modulo 10^9 + 7.

We apply that update n - 1 times, then sum all five counters for the total number of length-n strings.

Example: n = 2. After one update the counts add up to 10, matching the ten valid two-letter strings like ae, ea, ei, io, ua.

Time: O(n) Space: O(1)