Day 17 - Count Sorted Vowel Strings
Tags: leetcode, python, challenge
Published: 2021-01-17 17:33:03

## 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"].
```

__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

```python
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

```python
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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/x3v7huk0t0ycr5ql4qgi.png)


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/eff4nv93hfayx3d7k8pw.png)


## 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.