Count Vowels Permutation

TARGET DECK: Leetcode FILE TAGS: Hard

---

Intuition

• Make sure to understand preceded by vs. following.
• What tripped me up about this problem was that I kept trying to

Complexity

Runtime

$O(N)$ since we are iterating from 1 to N.

Space

$O(1)$

Code

Bottom Up with Recursion

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        # Bottom up coded recursively
        @cache
        def r(letter, level):
            if level == 1:
                return 1
 
            if letter == 'a':
                return r('i', level - 1) + r('e', level - 1) + r('u', level - 1)
            if letter == 'e':
                return r('i', level - 1) + r('a', level - 1)
            if letter == 'i':
                return r('o', level - 1) + r('e', level - 1)
            if letter == 'o':
                return r('i', level - 1)
            if letter == 'u':
                return r('i', level - 1) + r('o', level - 1)
 
        return (r('a', n) + r('e', n) + r('i', n) + r('o', n) + r('u', n)) % (10 ** 9 + 7)

Notes

Cards

START Basic Front: Count Vowels Permutation Back: Simulate through top down or bottom up the gathering of each vowel.

END

---

References

• Count Vowels Permutation