Count Number of Strings Using Grammar Rules in Python

Suppose we have a number n, we have to find the number of strings of length n can be generated using the following rules −

• Each character is a lower case vowel [a, e, i, o, u]

• "a" may only be followed by one "e"

• "e" may only be followed by any of "a" and "i"

• "i" may not be followed by another "i"

• "o" may only be followed by any of "i" and "u"

• "u" may only be followed by one "a"

If the result is very large, mod the result by 10^9 + 7.

So, if the input is like n = 2, then the output will be 10, as we can generate the following two letter strings: ["ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua"]

To solve this, we will follow these steps −

• m = 10^9 + 7

• if n is same as 0, then

  • return 0

• define five variables a, e, i, o, u, all are 1 initially

  • for _ in range 0 to n-1, do

    • a := e+i+u

    • e := a+i

    • i := e+o

    • o := i

    • u := i+o

• return (a + e + i + o + u) mod m

Let us see the following implementation to get better understanding −

Example

 Live Demo

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

ob = Solution()
print(ob.solve(3))

Input

3

Output

19