Search
⌘K
Prefix Sum

Count Vowels in Substrings

medium
DESCRIPTION

Write a function to efficiently count vowels within specified substrings of a given string.

The substrings will be given to you a list queries of [left, right] pairs, which correspond to the substring word[left:right + 1] in Python.

The function should return a list of integers, where each integer represents the vowel count for the corresponding query. You can assume the input string will only contain lowercase letters.

Your function should be optimized to run efficiently for a large number of queries.

Input:

word = "prefixsum"
queries = [[0, 2], [1, 4], [3, 5]]

Output: [1, 2, 1]

Explanation:

word[0:3] -> "pre" contains 1 vowels
word[1:5]-> "refi" contains 2 vowels
word[3:6]-> "fix" contains 1 vowels

Explanation

We can solve this question efficiently for a large number of queries of by using the Prefix Sum technique, with a slight modification.
Since our question is asking for the number of vowels in a substring, we can create a prefix sum array where prefix_sum[i] represents the number of vowels in the substring from index 0 to i - 1 (inclusive).
For example, for the string picture, our prefix_sum array would look like this:
picture01234560011231201234567prefix_sumword2 vowels in ​pictu (word[0:5])__0 vowels in ​p (word[0:1])0 vowels in ​empty string​ (word[0:0])
Remember that in Python, to get the substring from index i to j (inclusive), you need to use word[i:j + 1].
As an example, let's say our word is picture and we want the substring from index 0 to 3 (inclusive). We would use word[0:4] to get the substring pict, which has 1 vowel. This would be stored as prefix_sum[4].
With the prefix_sum array, we can now calculate the number of vowels in any range using the formula prefix_sum[right + 1] - prefix_sum[left], where right and left are the indices of the substring as specified by each entry in the queries array.
The visual below shows how we can use the prefix_sum array to calculate the number of vowels in the substring picture when [left, right] = [1, 4]:
picture01234560011321201234567prefix_sumright + 1wordleft
Using the prefix sum array count the vowels in ictu (word[1:5])
# of vowels in word[1:5] = prefix_sum[5] - prefix_sum[1]
So our solution has two parts:
1.) Create a prefix sum array prefix_sum where prefix_sum[i] stores the number of vowels in the substring word[0:i].
2.) Iterate over the queries array and calculate the number of vowels in the substring specified by each query using the formula prefix_sum[right + 1] - prefix_sum[left], and store each result that we return at the end.
Solution
class Solution:
    def vowelStrings(self, word, queries):
        vowels = set('aeiou')
        prefix_sum = [0] * (len(word) + 1)
        # Part 1: create the prefix sum array
        for i in range(1, len(word) + 1):
            is_vowel = word[i - 1] in vowels
            prefix_sum[i] = prefix_sum[i - 1] + (1 if is_vowel else 0)
        # Part 2: calculate the number of vowels in each query 
        result = []
        for left, right in queries:
            num_vowels = prefix_sum[right + 1] - prefix_sum[left]
            result.append(num_vowels)
        return result
Test Your Knowledge

Login to take the complexity quiz and track your progress

Complexity Analysis

Time Complexity: O(N + Q) where N is the length of the word string and Q is the number of queries. We iterate over the word string to create the prefix sum array (O(N)), then iterate over the queries array where each query takes O(1) time.

Space Complexity: O(N + Q) where N is the length of the word string and Q is the number of queries. We use O(N) space to store the prefix sum array, and O(Q) space to store the results of the queries.

Mark as read

Next: Subarray Sum Equals K

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations
Guided Practice
Recent interview questions
Learn More
Reading Progress

On This Page

Explanation

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsAnthropic SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift PremiumHello Interview Premium
Legal
Terms and ConditionsPrivacy PolicySecurity
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.

Count Vowels in Substrings | Hello Interview