The Problem
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
sis lexicographically sorted if for all validi,s[i]is the same as or comes befores[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
My Tests
import pytest
from .Day17_CountSortedVowelString import Solution
s = Solution()
@pytest.mark.parametrize(
"n,expected",
[
(1, 5),
(2, 15),
(33, 66045),
],
)
def test_count_vowel_strings(n, expected):
assert s.countVowelStrings(n) == expected
My Solution
class Solution:
def countVowelStrings(self, n: int) -> int:
if n == 0:
return 0
# Setup space to count [a, e, i, o, u] initialized with 1
counts = [1] * 5
# Let's do this n - 1 times basically
# Note if n == 1, count will be 5 and this loop is skipped
while n > 1:
n -= 1
# For each possible vowel
for i in range(1, len(counts)):
# Take the first iteration as an example where n == 2.
# Conceptually we start with [a = 1, e = 2, i = 1, o = 1, u = 1]
# Take i = 0. After counts[i] += counts[i - 1] we get [a = 1. e = 2, i = 4, o = 4, u = 5]
# And so on until we get [a = 1, e = 2, i = 3, o = 4, u = 5]
# Sum that you get 15
# ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
# Note the characteristic ot this. The numbers for each letter correspond to how many strings end with that letter.
# Because 'a' is lexicographically the smallest, only one string can end with it "aa". Because u is the largest, the greatest number of strings end with it.
counts[i] += counts[i - 1]
return sum(counts)
Analysis
My Commentary
I wish I could take credit for coming up with this clever solution but I can only take credit for remembering I read something very similar to this at some point in my life. I wish I could remember where so I could give proper credit. I find this kind of thinking helps with a lot of problems. Essentially breaking it down to the smallest possible problem and solving that over and over without getting distracted by the larger problem. My brain generally doesn't work that way but luckily this can be learned to some degree.
I added comments in the code so won't go further into the solution here.
Top comments (0)