1641-count-sorted-vowel-strings

Try it on leetcode

Description

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

 

Example 1:

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2:

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Example 3:

Input: n = 33
Output: 66045

 

Constraints:

• 1 <= n <= 50 

Solution(Python)

class Solution:
    def countVowelStrings(self, n: int) -> int:
        return self.math(n)

    # Time Complexity: O(5^n)
    def backtrack(self, n, last=0):
        if n == 0:
            return 1
        else:
            nb = 0
            for vowel in ["a", "e", "i", "o", "u"]:
                if last == "" or str(last) <= str(vowel):
                    nb += self.backtrack(n - 1, vowel)
            return nb

    # Time Complexity: O(n)
    @cache
    def topdowndp(self, n, last=0):
        if n == 0:
            return 1
        else:
            nb = 0
            for vowel in ["a", "e", "i", "o", "u"]:
                if last == "" or str(last) <= str(vowel):
                    nb += self.backtrack(n - 1, vowel)
            return nb

    # Time Complexity: O(n)
    def bottomup(self, n):
        dp = [[0] * 5 for _ in range(n)]
        dp[0] = [1] * 5

        for i in range(1, n):
            for j in range(5):
                for k in range(j, 5):
                    dp[i][j] += dp[i - 1][k]
        return sum(dp[-1])

    # Time Complexity: O(1)
    def math(self, n):
        return (n + 4) * (n + 3) * (n + 2) * (n + 1) // 24