Press "Enter" to skip to content

花花酱 LeetCode 1641. Count Sorted Vowel Strings

Given an integer n, return the number of strings of length n that consist only of vowels (aeiou) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid is[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
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Example 3:

Input: n = 33
Output: 66045

Solution: DP

dp[i][j] := # of strings of length i ends with j.

dp[i][j] = sum(dp[i – 1][[k]) 0 <= k <= j

Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++/O(n) Space

C++/O(1) Space

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website


Be First to Comment

Leave a Reply