Count Vowels in Substrings
MediumPrefix-sum a 0/1 indicator
Keep a running count of vowels, so any window's vowel-count is one subtraction.
The idea
Turn each character into 1 if it's a vowel, else 0, then take prefix sums. The vowel count of any substring becomes a single subtraction.
a
l
g
o
v
i
z
0
1
2
3
4
5
6
vowels0
Step 1 of 9. Turn each letter into 1 (vowel) or 0, then a running total lets any range be answered by subtraction. Values: a, l, g, o, v, i, z. vowels 0.
1/9
Optimal
timeO(n)spaceO(n)
Sum a boolean signal.
1const P = [0];2for (const c of s) P.push(P.at(-1) + (isVowel(c) ? 1 : 0));3const vowels = (l, r) => P[r + 1] - P[l];Input
- array
- [a, l, g, o, v, i, z]
Memory
- i
- —
Output
- vowels
- 0
- prefix
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "abie"
- Output:
- 4
- Explanation:
- Count vowel-only substrings using running lengths.
Example 2
- Input:
- s = "aeiou"
- Output:
- 15
- Explanation:
- All vowels → 15 substrings.
Example 3
- Input:
- s = "xyz"
- Output:
- 0
- Explanation:
- No vowels → 0.
Finished the walkthrough? Add it to your streak.