Explanation | C++ Solution
Lets suppose we have a string abaace. Lets see sum of number of vowels in each substring.\n\n\na(1)           b(0)           a(1)           a(1)          c(0)  
Lets suppose we have a string `abaace`. Lets see sum of number of vowels in each substring.\n\n```\na(1)           b(0)           a(1)           a(1)          c(0)        e(1)\nab(1)          ba(1)          aa(2)          ac(1)         ce(1)\naba(2)         baa(2)         aac(2)         ace(2)      \nabaa(3)        baac(2)        aace(3)\nabaac(3)       baace(3)\nabaace(4)\n```\n\nNow, we can see whenever a new character appears suppose `b` it is contributing to 2 string `ab` and `b` (similarly e is contributing to 5 strings ). So total sum when` b` appears becomes 0+1=1 (similarly for e it becomes 4+3+3+2+1+1 = 14. It is basically your diagonal sum from left to right for each row element of 1st col). Thus we can find for each character their contribution array . It will look like \n```\na b a a c e\n1 1 4 8 8 14\n```\nand now we can see this pattern and maintain a dp array if its non-vowel character its contribution is equal to dp[ i-1] else it `dp[i-1] +i+1`\n\n```\nlong long countVowels(string word) {\n        int n = word.length();\n        if(n==0)\n            return 0;\n        vector<long long> dp(n,0);\n        long long sum = 0;\n        for(int i = 0;i<n;i++)\n        {\n         if(word[i]==\'a\' || word[i]==\'e\' ||word[i]==\'i\' ||word[i]==\'o\' || word[i]==\'u\' )\n             dp[i] = i==0 ? 1 : dp[i-1]+i+1;\n            else\n                dp[i] = i==0? 0 : dp[i-1] ;\n        }\n        \n        for(int i = 0;i<n;i++)\n            sum += dp[i];\n        \n        return sum ;\n        \n    }\n```\nand then we can take the sum of whole array .
[]