[Java/C++/Python] DP, O(1) Time & Space
Explanation\ndp[n][k] means the number of strings constructed by at most k different characters.\n\nIf k = 1, use only u\nIf k = 2, use only o,u\nIf k = 3, use 
# **Explanation**\n`dp[n][k]` means the number of strings constructed by at most `k` different characters.\n\nIf `k = 1`, use only `u`\nIf `k = 2`, use only `o,u`\nIf `k = 3`, use only `i,o,u`\nIf `k = 4`, use only `e,i,o,u`\nIf `k = 5`, use only `a,e,i,o,u`\n<br>\n\n\n# Solution 1: Top Down\nTime `O(nk)`\nSpace `O(nk)`\nwhere k = 5\n\n**Python:**\n```py\n    def countVowelStrings(self, n):\n        seen = {}\n        def dp(n, k):\n            if k == 1 or n == 1: return k\n            if (n, k) in seen:\n                return seen[n, k]\n            seen[n, k] = sum(dp(n - 1, k) for k in xrange(1, k + 1))\n            return seen[n, k]\n        return dp(n, 5)\n```\n\n# Solution 2: Bottom Up\nTime `O(nk)`\nSpace `O(nk)`\nwhere k = 5\n\n**Java:**\n```java\n    public int countVowelStrings(int n) {\n        int[][] dp = new int[n + 1][6];\n        for (int i = 1; i <= n; ++i)\n            for (int k = 1; k <= 5; ++k)\n                dp[i][k] = dp[i][k - 1] + (i > 1 ? dp[i - 1][k] : 1);\n        return dp[n][5];\n    }\n```\n\n**C++:**\n```cpp\n    int countVowelStrings(int n) {\n        vector<vector<int>>dp(n + 1, vector<int>(6));\n        for (int i = 1; i <= n; ++i)\n            for (int k = 1; k <= 5; ++k)\n                dp[i][k] = dp[i][k - 1] + (i > 1 ? dp[i - 1][k] : 1);\n        return dp[n][5];\n    }\n```\n\n**Python:**\n```py\n    def countVowelStrings(self, n):\n        dp = [[1] * 6] + [[0] * 6 for i in xrange(n)]\n        for i in xrange(1, n + 1):\n            for k in xrange(1, 6):\n                dp[i][k] = dp[i][k - 1] + dp[i - 1][k]\n        return dp[n][5]\n```\n<br>\n\n# Solution 3: Bottom up, 1D DP\nTime `O(nk)`\nSpace `O(k)`\nwhere k = 5\n\n**Java:**\n```java\n    public int countVowelStrings(int n) {\n        int[] dp = new int[] {0, 1, 1, 1, 1, 1};\n        for (int i = 1; i <= n; ++i)\n            for (int k = 1; k <= 5; ++k)\n                dp[k] += dp[k - 1];\n        return dp[5];\n    }\n```\n\n**C++:**\n```cpp\n    int countVowelStrings(int n) {\n        vector<int> dp = {0,1,1,1,1,1};\n        for (int i = 1; i <= n; ++i)\n            for (int k = 1; k <= 5; ++k)\n                dp[k] += dp[k - 1];\n        return dp[5];\n    }\n```\n**Python:**\n```py\n    def countVowelStrings(self, n):\n        dp = [0] + [1] * 5\n        for i in xrange(1, n + 1):\n            for k in xrange(1, 6):\n                dp[k] += dp[k - 1]\n        return dp[5]\n```\n**Python3**\n```py\n    def countVowelStrings(self, n: int) -> int:\n        dp = [1] * 5\n        for i in range(n):\n            dp = accumulate(dp)\n        return list(dp)[-1]\n```\n<br>\n\n# Solution 4: Combination number\nNow we have `n` characters, we are going to insert 4 `l` inside.\nWe can add in the front, in the middle and in the end.\nHow many ways do we have?\nFor the 1st `l`, we have `n+1` position to insert.\nFor the 2nd `l`, we have `n+2` position to insert.\nFor the 3rd `l`, we have `n+3` position to insert.\nFor the 4th `l`, we have `n+4` position to insert.\nAlso 4 `l` are the same,\nthere are `(n + 1) * (n + 2) * (n + 3) * (n + 4) / 4!` ways.\n\nThe character before the 1st `l`, we set to `a`.\nThe character before the 2nd `l`, we set to `e`.\nThe character before the 3rd `l`, we set to `i`.\nThe character before the 4th `l`, we set to `o`.\nThe character before the 5th `l`, we set to `u`.\n\nWe get the one result for the oringinal problem.\n\nTime `O(1)`\nSpace `O(1)`\n\n**Java:**\n```java\n    public int countVowelStrings(int n) {\n        return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24;\n    }\n```\n**C++:**\n```cpp\n    int countVowelStrings(int n) {\n        return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24;\n    }\n```\n**Python:**\n```py\n    def countVowelStrings(self, n):\n        return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24\n```\n**Python3**\n@imaginary_user\n```py\n    def countVowelStrings(self, n: int) -> int:\n        return comb(n + 4, 4)\n```
[]