Python DP O(N) time O(1) space w/ comment
py\n\'\'\'\nw: dp\nh: when n = 1, we only have 5 choice,\n   wheb n = 2, we have 15 options, how they related\n   consider: [a, e, i, o, u]\n             [aa, a
```py\n\'\'\'\nw: dp\nh: when n = 1, we only have 5 choice,\n   wheb n = 2, we have 15 options, how they related\n   consider: [a, e, i, o, u]\n             [aa, ae, ai, ao, au  -- 5 strings\n                  ee, ei, eo, eu  -- 4 strings\n                      ii, io, iu  -- 3 strings\n                          oo, ou  -- 2 strings\n                              uu] -- 1 strings\n                              \n   we find a can be placed before any vowel, \n           e can be place before e, i, o, u; \n           i can be placed before i, o, u...\n           \n   so if n = 3, we can place a before any string when n = 2, which is 15\n                we can place e before string not start with a, which is 10\n                we can place i before strings not start with a, e, which is 6\n                \n   now see the pattern? \n\n   let\'s present the valid number of string for each vowel in a list:\n   n = 2, [5, 4, 3, 2, 1], 15 in total\n   n = 3, [15, 10, 6, 3, 1], 35 in total\n   n = 4, [35, 20, 10, 4, 1], 70 in total\n   ...\n   consider n = 2 and n = 3, from the end to the beginining, we can see\n   3 = 1 + 2, 6 = 3 + 3, 10 = 6 + 4, 15 = 10 + 5 \n   \n   now the pattern is clear, and you can try n=3 and n=4\n\'\'\'\n\nclass Solution:\n    def countVowelStrings(self, n: int) -> int:\n        # n = 1, base case\n        dp = [1, 1, 1, 1, 1]\n        # the valid number of string started with u is always 1\n        # or you can say dp[-1] is always 1 \n        u = 1\n        for i in range(n-1):\n            dp[4] = u\n            for j in range(1, 5)[::-1]:   \n                dp[j-1] = dp[j-1] + dp[j]\n\n        return sum(dp)\n```
['Dynamic Programming', 'Python']