## Count Sorted Vowel Strings  • Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
int countVowelStrings(int n) {
// dp := # of lexicographically sorted strings ends with 'a'
// dp := # of lexicographically sorted strings ends with 'e'
// dp := # of lexicographically sorted strings ends with 'i'
// dp := # of lexicographically sorted strings ends with 'o'
// dp := # of lexicographically sorted strings ends with 'u'
vector<int> dp(5, 1);

for (int i = 2; i <= n; ++i) {
vector<int> newDp(5);
for (int j = 0; j < 5; ++j)
for (int k = 0; k <= j; ++k)
newDp[j] += dp[k];
dp = move(newDp);
}

return accumulate(begin(dp), end(dp), 0);
}
};
``````

## JAVA

``````class Solution {
public int countVowelStrings(int n) {
// dp := # of lexicographically sorted strings ends with 'a'
// dp := # of lexicographically sorted strings ends with 'e'
// dp := # of lexicographically sorted strings ends with 'i'
// dp := # of lexicographically sorted strings ends with 'o'
// dp := # of lexicographically sorted strings ends with 'u'
int[] dp = new int;
Arrays.fill(dp, 1);

for (int i = 2; i <= n; ++i) {
int[] newDp = new int;
for (int j = 0; j < 5; ++j)
for (int k = 0; k <= j; ++k)
newDp[j] += dp[k];
dp = newDp;
}

return Arrays.stream(dp).sum();
}
}
``````