1641. Count Sorted Vowel Strings

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

Problem Summary

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 it satisfies: for all valid i, the position of s[i] in the alphabet is always the same as or before s[i+1].

Solution Approach

• The amount of data given by the problem is not large. The first idea is to use DFS traversal to generate a lookup table. The time complexity is O(1), and the space complexity is O(1).
• The second idea is to use the combination formula in mathematics to calculate the result. The problem is equivalent to assuming there are now n letters, and we need to take balls 4 times (we may choose not to take any) to divide the letters into 5 piles; ask how many ways there are. Once the method of taking is determined, the number of each letter, a, e, i, o, u, is determined. According to the problem, the letters must be sorted alphabetically, so the final string is also determined. Now we only need to focus on solving this combination problem. Transform the problem once more: equivalently, there are n+4 letters, and we take 4 times; ask how many ways there are. The +4 represents 4 empty operations, and taking them means taking nothing. According to the mathematical definition of combinations, the answer is C(n+4,4).

Code

package leetcode

// Solution 1: lookup table
func countVowelStrings(n int) int {
	res := []int{1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876, 230300, 249900, 270725, 292825, 316251}
	return res[n]
}

func makeTable() []int {
	res, array := 0, []int{}
	for i := 0; i < 51; i++ {
		countVowelStringsDFS(i, 0, []string{}, []string{"a", "e", "i", "o", "u"}, &res)
		array = append(array, res)
		res = 0
	}
	return array
}

func countVowelStringsDFS(n, index int, cur []string, vowels []string, res *int) {
	vowels = vowels[index:]
	if len(cur) == n {
		(*res)++
		return
	}
	for i := 0; i < len(vowels); i++ {
		cur = append(cur, vowels[i])
		countVowelStringsDFS(n, i, cur, vowels, res)
		cur = cur[:len(cur)-1]
	}
}

// Solution 2: mathematical method — combinations
func countVowelStrings1(n int) int {
	return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24
}