Given a string word
, return the sum of the number of vowels ('a'
, 'e'
, 'i'
, 'o'
, and 'u'
) in every substring of word
.
A substring is a contiguous (non-empty) sequence of characters within a string.
Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.
Example 1:
Input: word = "aba"
Output: 6
Explanation:
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6.
Example 2:
Input: word = "abc"
Output: 3
Explanation:
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.
Example 3:
Input: word = "ltcd"
Output: 0
Explanation: There are no vowels in any substring of "ltcd".
Constraints:
-
1 <= word.length <= 105
-
word
consists of lowercase English letters.
SOLUTION:
class Solution:
def countVowels(self, word: str) -> int:
n = len(word)
vows = {"a", "e", "i", "o", "u"}
initVowels = 0
vowelsTill = [initVowels]
for c in word:
if c in vows:
initVowels += 1
vowelsTill.append(initVowels)
total = 0
for i in range(n, -1, -1):
total += (2 * i - n) * vowelsTill[i]
return total
Top comments (3)
You can simplify it so much into a single line
You mean the whole function in one line? I tried submitting your code but it's giving wrong answer
Yeah I got incomplete logic at first hand, but here is the one liner that I tested
For easier reading