O(n) DP | Detailed explanation
There are great solutions using combinatorics. I also want to share a Dynamic Programming solution.\n\n# DP solution\nIf we go over a string/array from left to 
There are great solutions using combinatorics. I also want to share a Dynamic Programming solution.\n\n# DP solution\nIf we go over a string/array from left to right, we know that at each `i` index we have `i+1 **new**` contiguous substrings.\nExample: "a" has 1 substring, and at "ab" we have 2 *new substrings* ("ab", "b") so "ab" has total of 3 substrings.\n\nThis can hint to us that we can reuse the previously solved step to calculate the new step we take, but how?\n\nAt each index `i` we know that it contains at least the same amount of vowels as the previous index `i-1` since it contains all the substrings of the previous string, including the `i\'th` character.\nBut if the `i\'th` character is a vowel itself, then it also adds a vowel to each of the newly added substrings - `i+1` substrings as we\'ve seen previously, since all the substrings contain that character.\n\nExample the string `"abaef"`\n![image](https://assets.leetcode.com/users/images/a8bb0d35-0e00-45b6-a35a-944751f9a1ee_1654875720.1821039.png)\n\nAt the end, we **sum** all the vowels of the substrings and we will get the total result.\nThe base case of the DP, i.e. dp[0] is 1 if the first character is vowel and 0 otherwise.\n\n# Code\n```\nclass Solution:\n    # DP -> O(n) time and space\n    def countVowels(self, word: str) -> int:\n        n = len(word)\n        dp = [-1] * n\n        if self.is_vowel(word[0]):\n            dp[0] = 1\n        else:\n            dp[0] = 0\n            \n        for i in range(1, n):\n            dp[i] = dp[i-1]\n            if self.is_vowel(word[i]):\n                dp[i] += i+1\n        \n        return sum(dp)\n        \n    def is_vowel(self, char: str) -> bool:\n        return char in "aeiou"\n```\n
['Dynamic Programming']