DEV Community

loading...

Day 17 - Count Sorted Vowel Strings

ruarfff profile image Ruairí O'Brien ・2 min read

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 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"].
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: n = 33
Output: 66045
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Alt Text

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.

Discussion (0)

pic
Editor guide