✅🔥DP & 5 Variables Approach - C++/Java/Python
Intuition\n\n- Here we can observe a pattern to this problem.\n\n\n\t\t  a  e  i  o  u\n    n=1   1  1  1  1  1  /a, e, i, o, u\n    n=2   5  4  3  2  1  /a-> a
# Intuition\n\n- Here we can observe a pattern to this problem.\n\n```\n\t\t  a  e  i  o  u\n    n=1   1  1  1  1  1  /a, e, i, o, u\n    n=2   5  4  3  2  1  /a-> aa,ae,ai,ao,au | e-> ee,ei,eo,eu | i-> ii,io,iu | o-> oo,ou | u-> uu\n    n=3   15 10 6  3  1\n```\n\n- If we observe from last there will be only 1 element which will start with u. Every other element will have the count of previous count + next element count. As example\nin n=2, i will be previous i(1) + count of next element, o(2) \u2192 3\nin n=3, e will be previous e(4) + count of next element, i(6) \u2192 10\n\n# Approach 01\n1. Using ***5 variables.***\n1. Initialize variables a, e, i, o, and u to 1, representing the count of strings ending with each vowel.\n2. Iterate from n-1 to 0 using a loop, updating the count for each vowel as follows:\n   - Increment the count of strings ending with \'o\' (o += u).\n   - Increment the count of strings ending with \'i\' (i += o).\n   - Increment the count of strings ending with \'e\' (e += i).\n   - Increment the count of strings ending with \'a\' (a += e).\n3. After the loop, the sum of counts for all vowels (a+e+i+o+u) represents the total count of strings of length n that consist only of vowels and are lexicographically sorted.\n\n# Complexity\n- Time complexity: The time complexity of this solution is O(n), where algorithm iterates through the loop n times, and each iteration involves constant time operations.\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity is O(1) since we use a constant amount of space for variables regardless of the input size.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int countVowelStrings(int n) {\n        int a=1, e=1, i=1, o=1, u=1;\n        \n        while(--n){\n            o += u;\n            i += o;\n            e += i;\n            a += e;\n        }\n        \n        return a+e+i+o+u;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int countVowelStrings(int n) {\n        int a = 1, e = 1, i = 1, o = 1, u = 1;\n\n        while (--n > 0) {\n            o += u;\n            i += o;\n            e += i;\n            a += e;\n        }\n\n        return a + e + i + o + u;\n    }\n}\n```\n```python []\nclass Solution(object):\n    def countVowelStrings(self, n):\n        a, e, i, o, u = 1, 1, 1, 1, 1\n\n        while n > 1:\n            o += u\n            i += o\n            e += i\n            a += e\n            n -= 1\n\n        return a + e + i + o + u\n```\n\n---\n\n\n\n# Approach  02\n\n1. Using ***Dynamic Programing(dp).***\n2. Initialize a vector dp of size 5 (representing the vowels) with all elements set to 1. This vector will store the count of strings ending with each vowel.\n3. Iterate n-1 times (since we already have the count for n=1).\n4. In each iteration, update the count in the dp vector by summing up the counts of strings ending with each vowel from right to left. This step corresponds to extending the strings by adding one more character.\n5. After the iterations, the sum of counts in the dp vector represents the total number of strings of length n that can be formed using vowels.\n6. Return the sum as the result.\n\n\n# Complexity\n- Time complexity: The time complexity of this solution is O(3n) - The algorithm iterates n-1 times, and each iteration involves updating the vector in constant time.\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity is O(1) since we use a constant amount of space for variables regardless of the input size.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int countVowelStrings(int n) {\n        vector<int> dp(5, 1);\n        int ans = 0;\n        \n        while(--n){\n            for(int i=3; i>=0; i--){\n                dp[i] += dp[i+1];\n            }\n        }\n        \n        for(auto x:dp) ans += x;\n        \n        return ans;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int countVowelStrings(int n) {\n        int[] dp = new int[]{1, 1, 1, 1, 1};\n        int ans = 0;\n\n        while (--n > 0) {\n            for (int i = 3; i >= 0; i--) {\n                dp[i] += dp[i + 1];\n            }\n        }\n\n        for (int x : dp) {\n            ans += x;\n        }\n\n        return ans;\n    }\n}\n```\n```python []\nclass Solution(object):\n    def countVowelStrings(self, n):\n        dp = [[0] * 5 for _ in range(n + 1)]\n\n        for j in range(5):\n            dp[1][j] = 1\n\n        for i in range(2, n + 1):\n            for j in range(5):\n                for k in range(j, 5):\n                    dp[i][j] += dp[i - 1][k]\n\n        result = sum(dp[n])\n        return result\n```\n\n---\n\n> **Please upvote this solution**\n>
['Dynamic Programming', 'Python', 'C++', 'Java', 'Python3']