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
Related Topics:
Dynamic Programming
We use cnt[5] to store the count of strings ending with aeiou respectively.
When n == 1, int cnt[5] = {1,1,1,1,1}.
When going from n to n + 1, the strings of length n ending with a can be appended with aeiou, and thus contributes its count cnt[0] to next[0..4] where int next[5] is the cnt for strings of length n + 1.
Similarly, cnt[1] contributes to next[1..4]. cnt[2] contributes to next[2..4]. And cnt[4] contributes to next[4].
After each iteration, we swap next back into cnt and continue.
After n - 1 iterations, we return the sum of cnt array.
// OJ: https://leetcode.com/problems/count-sorted-vowel-strings/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int countVowelStrings(int n) {
int cnt[5] = {1,1,1,1,1};
while (--n) {
int next[5] = {};
for (int i = 0; i < 5; ++i) {
for (int j = i; j < 5; ++j) next[j] += cnt[i];
}
swap(cnt, next);
}
return accumulate(begin(cnt), end(cnt), 0);
}
};