_2063. Vowels of All Substrings.md

2063. Vowels of All Substrings

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : March 11, 2025

Last updated : March 11, 2025

---

Related Topics : Math, String, Dynamic Programming, Combinatorics

Acceptance Rate : 54.53 %

---

Notes and Scratch Work

n = Total length of word
v = Number of vowels in word

aba
    a   1
    b   0
    a   1
    ab  1
    ba  1
    aba 2

This is the same as doing "aaaa" instead of "aba" --> becomes 4 choose 2 = 6

abc
    a   1
    b   0
    c   0
    ab  1
    bc  0
    abc 1

    abc -> aaa -> 3 choose 1 = 3

abba
    a       1
    b       0
    b       0
    a       1

    ab      1
    bb      0
    ba      1

    abb     1
    bba     1

    abba    2

    Total: (1)+(1+1)+(1+1+1)+(2) = 8
    abba --> aaaba --> aaaaaa --> 6 choose 2 = 15 WRONG
    abba -> aaba --> aaaaa -> 5 choose 2 = 10 WRONG
    abba -> aaaa --> 4 choose 2 = 6 WRONG

    contributions:
    a   4
    b   0
    b   0
    a   4

abab
    a       1
    b       0
    a       1
    b       0

    ab      1
    ba      1
    ab      1

    aba     2
    bab     1

    abab    2

    Total = 2+3+3+2 = 10

    contributions:
    a   4 = 0 * 3 + 4
    b   0
    a   6 = (left * right) + total string length = 2 * 1 + 4
    b   0

Realization: Each vowel contributes the following to the output:

$$(\text{characters left}) * (\text{characters right}) + \text{word length}$$

---

Solutions

• m2063 v1.py
• m2063 v2.py
• m2063 v3 oneliner.py

Python

m2063 v1.py

class Solution:
    def countVowels(self, word: str) -> int:
        vows = set('aeiou')
        output = 0
        for i, c in enumerate(word) :
            if c in vows :
                output += i * (len(word) - i - 1) + len(word)
        return output

m2063 v2.py

class Solution:
    def countVowels(self, word: str) -> int:
        vows = set('aeiou')
        return sum(i * (len(word) - i - 1) + len(word) for i, c in enumerate(word) if c in vows)

m2063 v3 oneliner.py

class Solution:
    def countVowels(self, word: str) -> int:
        return sum(i * (len(word) - i - 1) + len(word) for i, c in enumerate(word) if c in 'aeiou')