Problem statement

https://leetcode.com/problems/count-vowels-permutation/

Solution 1

Let us reformulate problem statement: we can have the following cases:

  1. If last letter is a, then previous letters can be e, i, u
  2. If last letter is e, then previous letters can be a, i
  3. If last letter is i, then previous letters can be e, o
  4. If last letter is o, then previous letter can be only i
  5. If last letter is u, then previous letters can be i, o.

So, we just keep 5 states for letters a, e, i, o, u and update it n-1 times.

Complexity

Time complexity is O(n), space complexity is O(1).

Code

class Solution:
    def countVowelPermutation(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

Solution 2

Actually what we have in this problem is linear recurrent and it can be solved using power of matrices. Let mat be matrix of possible transitions, then what we need to do is just multiply starting vector [1, 1, 1, 1, 1] by this matrix n-1 times, or which is equivalent for this problem is sum of elements of matrix mat^{n-1}.

Complexity

Time complexity is O(m^3*log n) = O(125 * log n), where m is order of our reccurence. It is O(log n) but with quite big constant so I prefer to make this more careful analysis. Space complexity is O(m^2) = O(25).

Code

import numpy as np

class Solution:
    def countVowelPermutation(self, n): 
        def power(mat, n, M):
            result = np.eye(len(mat), dtype = int)
            while n > 0:
                if n%2: result = np.dot(mat, result) % M
                mat = np.dot(mat, mat) % M
                n //= 2
            return result
        
        M = 10**9 + 7
        mat = np.matrix([[0,1,0,0,0], [1,0,1,0,0], [1,1,0,1,1], [0,0,1,0,1], [1,0,0,0,0]])      
        return np.sum(power(mat, n-1, M)) % M