Dynamic Programming for Counting Vowels

This is an interesting problem: https://leetcode.com/problems/count-sorted-vowel-strings/

1641. Count Sorted Vowel Strings

Medium

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 

Accepted

5,436

Submissions

7,006

If you look at the hints to this problem, they talk about recursive solutions. I think a DP (Dynamic Programming) suits quite well to it. And the way that I like to do DP is by construction: start by solving the problem for n=1, then use that to solve the problem for n=2, and eventually you get to n=N (the target). The space here will be constant, just holding 5 values for each vowel. When n=1, the solution is given. From that point on, look at the previous solution and do the calculation based on the rules given. The time complexity will be O(5*N), or O(N). Hence O(N)-time, O(1)-space. Code is below, cheers, ACC.

Btw, I didn't know that Richard Bellman wrote a biography right before his death, which was too soon (he was only 63...).

public int CountVowelStrings(int n)
{
    int[] dpPrevious = new int[5];
    int[] dpCurrent = new int[5];

    for (int i = 0; i < dpPrevious.Length; i++) dpPrevious[i] = 1;
    int count = 5;

    for (int i = 2; i <= n; i++)
    {
        int partial = 0;
        count = 0;
        for (int j = 0; j < dpPrevious.Length; j++)
        {
            partial += dpPrevious[j];
            dpCurrent[j] = partial;
            count += dpCurrent[j];
            dpPrevious[j] = dpCurrent[j];
        }
    }

    return count;
}