Leetcode 1641. Count Sorted Vowel Strings

Problem Explanation

We are given an integer n. The challenge is to return the number of strings of length n that consist only of the vowel letters (a, e, i, o, u) and are lexicographically sorted. A string s is considered lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Let's take an example where n = 2. All possible combinations of length 2 using only vowels would be ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]. Here, "ea" would not be considered a valid string as 'e' comes after 'a' in the alphabet.

Solution Walkthrough

The problem boils down to solving a combinatorics problem. The solution uses dynamic programming to solve it. It uses an array dp[5] to keep track of the number of lexicographically sorted strings ending with each vowel. dp[0], dp[1], dp[2], dp[3] and dp[4] respectively denote the counts of strings ending with 'a', 'e', 'i', 'o' and 'u'. The dp array is initialized with ones because there is exactly one string of length 1 ending with each vowel.

Then, for each length from 2 to n, the script updates the dp array. For each vowel, it sums the counts of strings (from the previous length) ending with that vowel or a vowel that precedes it. This is based on the understanding that a string of length i ending with a certain vowel can be formed by appending that vowel to the end of a string of length i-1 ending with that vowel or a vowel that precedes it. After updating the dp array for all lengths up to n, the script returns the sum of counts in the dp array, which is the total number of lexicographically sorted strings of length n.

Let's take an example where n = 3. The initial dp array is [1, 1, 1, 1, 1]. In the first iteration, when the string length is 2, the dp array becomes [1, 2, 3, 4, 5]. This means that there is 1 string ending with 'a', 2 ending with 'e', 3 ending with 'i', 4 ending with 'o' and 5 ending with 'u'. In the second iteration, when the string length is 3, the dp array becomes [1, 3, 6, 10, 15]. Therefore, the total number of strings of length 3 is 1 + 3 + 6 + 10 + 15 = 35.

Python Solution

1
2python
3class Solution:
4    def countVowelStrings(self, n: int) -> int:
5        dp = [1]*5
6        for _ in range(2, n + 1):
7            for i in reversed(range(5)):
8                dp[i] = sum(dp[:i+1])
9        return sum(dp)

Java Solution

1
2java
3class Solution {
4    public int countVowelStrings(int n) {
5        int[] dp = new int[5];
6        Arrays.fill(dp, 1);
7        for (int _i = 2; _i <= n; _i++) {
8            for (int i = 3; i >= 0; i--) {
9                dp[i] += dp[i + 1];
10            }
11        }
12        return dp[0] + dp[1] + dp[2] + dp[3] + dp[4];
13    }
14}

JavaScript Solution

1
2javascript
3class Solution {
4    countVowelStrings(n) {
5        let dp = new Array(5).fill(1);
6        for (let _i = 2; _i <= n; _i++) {
7            for (let i = 3; i >= 0; i--) {
8                dp[i] += dp[i + 1];
9            }
10        }
11        return dp.reduce((a, b) => a + b, 0);
12    }
13}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int countVowelStrings(int n) {
6        vector<int> dp(5, 1);
7        for (int _i = 2; _i <= n; ++_i) {
8            for (int i = 3; i >= 0; --i) {
9                dp[i] += dp[i + 1];
10            }
11        }
12        return accumulate(begin(dp), end(dp), 0);
13    }
14};

C# Solution

1
2csharp
3public class Solution {
4    public int CountVowelStrings(int n) {
5        int[] dp = new int[5];
6        Array.Fill(dp, 1);
7        for (int _i = 2; _i <= n; _i++) {
8            for (int i = 3; i >= 0; i--) {
9                dp[i] += dp[i + 1];
10            }
11        }
12        return dp.Sum();
13    }
14}

In all the solutions above, dp is an array that counts the number of lexicographically sorted strings ending with each vowel. It is updated for each length of string from 2 to n. At the end, the sum of counts in the dp array is returned as the total number of lexicographically sorted strings.## Scala Solution

The Scala solution follows the same logic as the other implemented solutions. The only major difference is due to Scala's language syntax and style. Below is the Scala solution.

1
2scala
3class Solution {
4  def countVowelStrings(n: Int): Int = {
5    val dp = Array.fill(5)(1)
6    for (_ <- 2 to n) {
7      for (i <- 3 to 0 by -1) {
8        dp(i) += dp(i + 1)
9      }
10    }
11    dp.sum
12  }
13}

In the Scala solution, we first initialize an array of 5 elements, all set to 1, representing the number of strings ending with each vowel. We then use a for-comprehension to iterate over each length (from 2 to n) and each vowel index (from 3 to 0 in reverse order). For each vowel, we add the count of strings ending with the next vowel to its own count, achieving the same updating as in the other solutions. Finally, we return the sum of the counts in the dp array.

Ruby Solution

Now let's look at the Ruby solution. Ruby also has its own style and syntax, but the overall logic remains consistent.

1
2ruby
3class Solution
4  def count_vowel_strings(n)
5    dp = Array.new(5, 1)
6    2.upto(n) do |_|
7      (3.downto(0)) { |i| dp[i] += dp[i + 1] }
8    end
9    dp.sum
10  end
11end

The Ruby solution begins by creating a new array of size 5, all elements initialized to 1. The method upto is then used to iterate from 2 to n, and within that loop, the method downto is used to iterate from 3 to 0. This allows us to update the array in the intended way. Finally, the sum of the counts in the dp array is returned.

All the solutions given in Python, Java, JavaScript, C++, C#, Scala, Ruby employ dynamic programming with a minor tweak to calculate the number of strings of length n that can be formed using vowels and that are lexicographically sorted. Hence, the presented problem is a great example to understand dynamic programming along with a combinatorics problem.