# 1641. Count Sorted Vowel Strings     • Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int countVowelStrings(int n) { // dp := the number of lexicographically sorted string that end in 'a' // dp := the number of lexicographically sorted string that end in 'e' // dp := the number of lexicographically sorted string that end in 'i' // dp := the number of lexicographically sorted string that end in 'o' // dp := the number of lexicographically sorted string that end in 'u' vector dp(5, 1); for (int i = 2; i <= n; ++i) { vector 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(dp.begin(), dp.end(), 0); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int countVowelStrings(int n) { // dp := the number of lexicographically sorted string that end in 'a' // dp := the number of lexicographically sorted string that end in 'e' // dp := the number of lexicographically sorted string that end in 'i' // dp := the number of lexicographically sorted string that end in 'o' // dp := the number of lexicographically sorted string that end in '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(); } }