DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Vowels of All Substrings

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
Enter fullscreen mode Exit fullscreen mode

Top comments (3)

Collapse
 
naveennamani profile image
naveennamani

You can simplify it so much into a single line

total = sum((len(word) for c in word if c in ["a", "e", "i", "o", "u"]))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
theabbie profile image
Abhishek Chaudhary

You mean the whole function in one line? I tried submitting your code but it's giving wrong answer

Collapse
 
naveennamani profile image
naveennamani

Yeah I got incomplete logic at first hand, but here is the one liner that I tested

total = sum((i+1)*(len(word)-i) for i, c in enumerate(word) if c in ["a", "e", "i", "o", "u"])
Enter fullscreen mode Exit fullscreen mode

For easier reading

total = sum(
    (i+1)*(len(word)-i)
    for i, c in enumerate(word)
    if c in ["a", "e", "i", "o", "u"]
)
Enter fullscreen mode Exit fullscreen mode

program