Python O(n) by DP//math [w/ Comment]
Hint:\n\nDefine dp[i] = count of vowels of substring ending at index i, i is from 0 to len(word)-1\n\nState Transfer function\n\n\nIf word[i] is vowel:\n\t\t# c
**Hint**:\n\nDefine dp[i] = **count of vowels** of **substring ending at index i**, i is from 0 to len(word)-1\n\n**State Transfer function**\n\n```\nIf word[i] is vowel:\n\t\t# current index i contributes extra (i+1) substring with current vowel character, which is ending at index i\n\t\tdp[i] = dp[i-1] + (i+1)\n```\n\n```\nIf word[i] is not vowel:\n\t\t# current index i has no contribution\n\t\tdp[i] = dp[i-1] + 0 = dp[i-1]\n```\n\n---\n\nFinal answer = **count of vowels of all substrings**\n= dp[0] + dp[1] + ... + dp[ len(word)-1 ]\n= **summation of all dp table values**\n= sum( dp(i) for i in range( len(word) ) ) \n\n---\n\n**Implementation** by top-down DP in Python\n\n```\nclass Solution:\n    def countVowels(self, word: str) -> int:\n    \n        vowels = set("aeiou")\n        \n        @cache\n        def dp( i ):\n            \n            ## Base case:\n            if i == 0:\n                \n                return 1 if word[i] in vowels else 0\n            \n            \n            ## General cases:\n            prev = dp(i-1)\n            \n            if word[i] in vowels:\n                # current index i contributes (i+1) substring with current vowel character, which is ending at index i\n                return prev + (i+1)\n            else:\n                # current index i has not contribution\n                return prev\n        \n        # -----------------------------------------\n        return sum( [dp(i) for i in range(len(word))] )\n```\n\n---\n\n**Implementation** by bottom-up DP in Python\n\n```\nclass Solution:\n    def countVowels(self, word: str) -> int:\n        \n        vowels = set("aeiou")\n        \n\n        \n        # {-1: 0} is for vowel count = 0 on empty string\n        dp = {-1: 0}\n        \n        for i, char in enumerate(word):\n            \n            prev_vowel_count = dp[i-1]\n            \n            if char in vowels:\n                \n                # current index i contributes (i+1) substring with current vowel character, which is ending at index i\n                cur_vowel_count = prev_vowel_count + (i + 1)\n                \n            else:\n                # current index i has not contribution\n                cur_vowel_count = prev_vowel_count\n\n\n            dp[i] = cur_vowel_count\n            \n\n        return sum( dp.values() )\n```\n\n---\n\n**Implementation** by math in Python\n\n```\nclass Solution:\n    def countVowels(self, word: str) -> int:\n        \n        n = len(word)\n        vowel = set("aeiou")\n        \n        count = 0\n        \n        for i, char in enumerate(word):\n            \n            if char in vowel:\n                \n                # curent vowel char can be covered by s[start:end]\n                \n                # start is from index 0 to i inclusively, total i+1 choices\n                # end is from index i to n-1 inclusively, total n-i choices\n                \n                start_combination, end_combination = (i+1), (n-i)\n                count += start_combination * end_combination\n        \n        return count\n```
['Math', 'String', 'Dynamic Programming', 'Python']