✅ 5 C++ Solutions || 1 Backtracking,1 Recursion(TLE), 1 DP and 2 other Approach || Easy
As you scroll down, there is a optimized solution given than the previous one.\n\n #####  Approach-1: Recursion (Shows TLE for n>40 and works for n<=40)\n\nHere
### **As you scroll down, there is a optimized solution given than the previous one.**\n\n* #####  **Approach-1**: **Recursion** *(Shows **TLE for n>40 and works for n<=40**)*\n\nHere, every next call for a decreased value of n gives us the required result and then we will add vowels at the start of result we get to get the strings of desired length. ( **i.e for n=2**, solver(n-1) or here, **solver(1) gives us the sorted vowels strings of length=1** and then we will **add up vowels again at the start of the sorted vowels strings we get, (maintaining the lexicographically sorted order) to get the sorted vowels strings of length=2**) \n\n***-->CODE:***\n```\nclass Solution\n{\nprivate:\n    vector<char> vowels = {\'a\', \'e\', \'i\', \'o\', \'u\'};\npublic:\n    vector<string> solver(int n)\n    {\n        if (n == 0)\n        return {""};\n        \n        vector<string> asf = solver(n - 1);\n        vector<string> ans;\n\n        for (string i : asf)\n        {\n            for (char j : vowels)\n            {\n\t\t\t \t//check that the character you want to insert \n\t\t\t\t//is smaller than the first character of asf(answer so far) string \n\t\t\t\t//to maintain lexicographically sorted order\n                if (j <= i[0] || asf.size() == 1)\n                    ans.push_back(j + i);\n                else\n                    break;\n            }\n        }\n        return ans;\n    }\n    int countVowelStrings(int n)\n    {\n        vector<string> ans = solver(n);\n        return ans.size();\n    }\n};\n```\n\n* #####  **Approach-2**: **Backtrack** *(**Gets submitted**)*\n\n***-->CODE:***\n```\n void solver(vector<vector<char>> &ans, vector<char> &temp, vector<char> &vowels, int start, int n)\n    {\n        if (temp.size() == n)\n        {   ans.push_back(temp);\n            return;\n        }\n        \n        for (int i = start; i < vowels.size(); i++)\n        {\n            temp.push_back(vowels[i]);\n            solver(ans, temp, vowels, i, n);\n            temp.pop_back();\n        }\n        return;\n    }\n\n    int countVowelStrings(int n)\n    {   vector<char> vowels = {\'a\', \'e\', \'i\', \'o\', \'u\'};\n        vector<char> temp;\n        vector<vector<char>> ans;\n        solver(ans, temp, vowels, 0, n);\n        return ans.size();\n    }\n```\n\n* ##### **Approach-3**: Dynamic Programming(**DP**), **Time:O(n), Space:O(n)**\n-Here, you can observe: \n```\nn=1, dp = {1,2,3,4,5}      return 5\nn=2, dp = {1,3,6,10,15}    return 15\nn=3, dp = {1,4,10,20,35}   return 35\n```\n\n***-->CODE:***\n```\n  int countVowelStrings(int n) {\n        vector<int> dp(5, 1);\n        for(int i=0; i<n; i++){\n            for(int j=1; j<5; j++){\n                dp[j] += dp[j-1];\n            }\n        }\n        return dp[4];\n    }\n```\n\n* ##### **Approach-4:**  **Time:O(n), Space:O(1)**\n\n-Here, you can observe a pattern : \n```\n\t\t   a  e  i  o  u\n ->  n=1   1  1  1  1  1  \n ->  n=2   5  4  3  2  1  \n ->  n=3   15 10 6  3  1\n```\n\t\nIf we observe every other element will have the count of previous count value + next element count for the same n. As example\nn=2,  a(in n=1) + count of next element, i.e e(in n=2) =5\nn=3,  e(in n=2) + count of next element, i.e i(in n=3) =10\n\n***-->CODE:***\n   ```\n int countVowelStrings(int n)\n    {\n        int a, e, i, o, u;\n        a = e = i = o = u = 1;\n        while (--n)\n        {\n            o += u;\n            i += o;\n            e += i;\n            a += e;\n        }\n        return a + e + i + o + u;\n    }\n```\n\n* ##### **Approach-5:** **Time:O(1), Space:O(1)**\n**Visit for detailed explanation**: [https://leetcode.com/problems/count-sorted-vowel-strings/discuss/1021493/One-line-solution-or-Math-or-No-DP-no-Big-Integers-or-O(1)-time-space](http://) \n\n***-->CODE:***\n\n```\nclass Solution {\npublic:\n    int countVowelStrings(int n) {\n        return (n+4)*(n+3)*(n+2)*(n+1) / 24;\n    }\n};\n```\n
['Math', 'Dynamic Programming', 'Backtracking', 'Recursion', 'C', 'Combinatorics']