[Python] DP, no extra memory
Intuition\nWe can approach this problem with DP. Let\'s count total number of vowels in the substrings of word prefix word[0..i] and call it DP(i). \nThus given
# Intuition\nWe can approach this problem with DP. Let\'s count total number of vowels in the substrings of ``word`` prefix ``word[0..i]`` and call it ``DP(i)``. \nThus given we have ``DP(i-1)`` we can calculate ``DP(i)`` in the following way:\n1. If ``word[i]`` is a consonant, then total number of vowels in all substrings of the prefix ``word[0:i]`` will be the same as the number of vowels of all substrings of the prefix ``word[0:i-1]``, thus ``DP(i) = DP(i-1)``, assuming ``DP(-1) = 0`` - number of vowels in substrings of an empty string.\n2. If ``word[i]`` is a vowel, we add exactly ``len(word[0:i])`` vowels since we will have substrings ``word[0:i-1] + word[i]``, ``word[1:i-1] + word[i]``,... ``word[i-1:i-1] + word[i]``.\nFor the total value we need to sum up values for the substrings - all ``DP(i)``\n\n# Approach\nWe don\'t need extra memory apart from two variables to calculate the result. We actually need only to store the result and previous ``DP`` value. All we need is to iterate over the string, check if consequtive character is a vowel and add current prefix length to the previous ``DP`` value, and accumulate it into the ``result``.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution:\n    def countVowels(self, word: str) -> int:\n        result = 0\n        current = 0\n        for i, c in enumerate(word):\n            if c in "aeiou":\n                current += (i+1)\n            result += current\n        return result\n```\n\n\nShall you have any questions - please feel free to ask, and upvote if you like it!
['Python3']