C++ | O(n) | Brute to Optimal | Best Explanation
The Brute force approach to this problem is very simple. Just go through all the substring of the string and find the number of vowels in all those substrings a
The **Brute force** approach to this problem is very simple. Just go through all the substring of the string and find the number of vowels in all those substrings and add them.\n\nBut, it would take O(n^2) to find all the subtrings which will result in **TLE.**\n\nThe **better solution** would be to check -  the number of times every character would occur in any substring.And, if we observe carefully, this is what we want - i.e, the sum of vowels in every substring. So, why not find the occurance of evry character in each substring. This will eventually give us the same result. **Right?**\n\nFor example -> the 0th index character would occur in substring starting from 0 and ending at i. Where, i =(0 to n).\n\n\n Ex- s= "aba"\n Let us say, first a as a1 and second a as a2 to avoid confusion.\n\n a1 -> occurs in substring "a", "ab", "aba" . Count 3\n b -> occurs in substring "ab","b", "ba","aba".  Count 4\n a2->  occurs in substring "aba", "ba", "a".  Count 3\n \n **Now, the question is How to get that count?**\n And ths answer for that is - \n For each character,  we will store no. of substrings starting with that character + the number of substrings formed by the previous characters containing this character \u2013 the number of substrings formed by the previous characters only.\nAnd this will be **dp[i-1] + (n-i) -i**\n\n Now, when we got this value, that is number of times each character will occur in any subtring. Then , we will just check if the character is a vowel or not. If vowel, then add the count of number of times that character will occur in any substring.We will be using an array/vector to store the count.\n\n\n\n**Time Complexity :- O(n)**\n\nBelow is a C++ solution for the same.\n\n\n```\nclass Solution {\npublic:\n    bool isVowel(char ch){\n        if(ch==\'a\' or ch==\'e\' or ch==\'i\' or ch==\'o\' or ch==\'u\')\n            return true;\n        return false;\n    }\n    long long countVowels(string word) {\n        int n=word.size();\n        long long int ans=0;\n        vector<long long int> dp;\n \n        for (int i = 0; i < n; i++) {\n            if (i == 0)\n                dp.push_back(n);\n            else\n                dp.push_back((n - i) + dp[i - 1] - i);\n        }\n        for (int i = 0; i < n; i++)\n            if(isVowel(word[i]))\n                ans += dp[i];\n        return ans;\n    }\n    \n};\n\n```\nHope it helps!\nPlease upvote if you like.\n\nThank you!
['C']