Prefix Sum
Count Vowels in Substrings
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
class Solution:def vowelStrings(self, word, queries):vowels = set('aeiou')prefix_sum = [0] * (len(word) + 1)# Part 1: create the prefix sum arrayfor i in range(1, len(word) + 1):is_vowel = word[i - 1] in vowelsprefix_sum[i] = prefix_sum[i - 1] + (1 if is_vowel else 0)# Part 2: calculate the number of vowels in each queryresult = []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
Unlock Premium Coding Content
On This Page
Your account is free and you can post anonymously if you choose.