O(n) | Runtime: 0 ms, faster than 100.00% | Intuition Explained
Appraoch 1 \n\nIntution : At First glance it is easy to understand that this is backtracking related question. All we have to do is count all the combination th
**Appraoch 1 **\n\nIntution : At First glance it is easy to understand that this is backtracking related question. All we have to do is count all the combination that can generate string of length n and will be of sorted order.\n\nIf we go with backtracking the time complexity will be 2^n. **(OH MY GOD)**. It is too slow. Can we do something better. Lets analyize few test cases to understand the intution may be we can figure out something better.\n\n1. n=1\n\tnumber of possible string will be 5 (a,e,i,o,u)\n\t\n2.  n=2\na_  Here we have 5 possible choice for string starting with a\ne_  Here we have 4 possible choice for string starting with e\ni_   Here we have 3 possible choice for string starting with i\no_  Here we have 2 possible choice for string starting with o\nu_  Here we have 1 possible choice for string starting with u\n\nwe have 5 possible choice after a because we need to maintain sorted or so after a we can only place a e i o u ( 5 characters). Similar explaination for string starting with e,i,o,u\n\nTotal String 5+4+3+2+1 =15\n\n3. n=3\n\naa5\nae4\nai3\nao2\nau1\ntotal 15\n\nee4\nei3\neo2\neu1\n\ntotal = 10\n\nii3\nio2\niu1\n\ntotal = 6\n\noo2\nou1\n\ntotal = 3\n\nuu1\ntotal=1\n\nso sum will be\n\n15+10+6+3+1 = 35\n\nSo for n=2\nwe have\n[5,4,3,2,1]\n\nn=3\n[15,10,6,3,1]\n\nDo you see the pattern yet? C\'mon think a bit..\n\nFor array of n=3, element at 0th index is derived from prefix sum of n=2 from 0th to 4th index.\nsimilarly element at 1th index is derived from prefix sum of n=2 from 1 to 4th index and so on forth.\n\nThis is the intituion behind the solution in the code below. If you undestand the intution then try writing the solution on your own. Hope it helps.\n\n\n\n\n\n\n\n```\nclass Solution {\n    public int countVowelStrings(int n) {\n        \n        if(n==1)\n            return 5;\n        \n        if(n==2)\n            return 15;\n        \n        int arr[] = {5,4,3,2,1};\n\n        int sum=0;\n        \n        for(int i=3;i<=n;i++) {\n            sum=0;\n\t\t\t//this inner loop will always take constant iteration i.e. 5. So time complexity is O(1) for this\n            for(int j=3;j>=0;j--) {\n                arr[j]=arr[j]+arr[j+1];\n                sum+=arr[j];\n            }\n        }\n        \n        return sum+1;\n      \n    }\n}\n```\n\nT(n) O(5*n) = O(n_\nSpace O(1)\n\n**Approach 2 :**\nIt is still in progress, but i think we can do some mathematical calculation. Once solution is build I will paste it here.\n\n\nPlease upvote if it helps.~~~~!!!!~~~~~~
['Backtracking', 'Prefix Sum']