Problem statement

https://binarysearch.com/problems/Grammar-Rules/

Solution

Equal to Leetcode 1220. Count Vowels Permutation.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, n):
        a, e, i, o, u, M = 1, 1, 1, 1, 1, 10**9 + 7
        for _ in range(n-1):
            a, e, i, o, u = (e + i + u)%M, (a + i)%M, (e + o)%M, i%M, (i + o)%M
        
        return (a + e + i + o + u)%M