## 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.

###### EXAMPLES

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`

Run your code to see results here

## 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:

With the prefix_sum array, we can now calculate the nummber 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]:

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.

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

## Complexity Analysis

**Time Complexity**: O(N + Q), where N is the length of the word string and Q is the number of queries in the queries array. We iterate over the word string to create the prefix sum array, which takes O(N) time. Then, we iterate over the queries array to calculate the number of vowels in each query. Each iteration takes O(1) time, so the total time complexity is O(N + Q).

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

Loading comments...