You are given a 0-indexed array of strings words and a 2D array of integers queries.
Each query queries[i] = [li, ri] asks us to find the number of strings present in the range li to ri (both inclusive) of words that start and end with a vowel.
Return an array ans of size queries.length, where ans[i] is the answer to the ith query.
Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.
Example 1:
Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]] Output: [2,3,0] Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e". The answer to the query [0,2] is 2 (strings "aba" and "ece"). to query [1,4] is 3 (strings "ece", "aa", "e"). to query [1,1] is 0. We return [2,3,0].
Example 2:
Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]] Output: [3,2,1] Explanation: Every string satisfies the conditions, so we return [3,2,1].
Constraints:
1 <= words.length <= 1051 <= words[i].length <= 40words[i] consists only of lowercase English letters.sum(words[i].length) <= 3 * 1051 <= queries.length <= 1050 <= li <= ri < words.lengthProblem Overview: You receive an array of words and multiple queries. Each query asks how many words in a given index range start and end with a vowel (a, e, i, o, u). The task is to return the count for every query efficiently.
Approach 1: Direct Iteration for Each Query (Time: O(n * q), Space: O(1))
The most straightforward solution processes each query independently. For every query range [l, r], iterate through the words from index l to r. For each word, check whether the first and last characters belong to the vowel set. Increment a counter when the condition is satisfied. This method requires only constant extra memory and is simple to implement, but it becomes slow when the number of queries is large because the same indices may be scanned repeatedly.
Approach 2: Prefix Sum Array (Time: O(n + q), Space: O(n))
The optimized solution precomputes information so each query can be answered in constant time. First iterate through the array of words and create a binary array where 1 means the word starts and ends with a vowel and 0 otherwise. Then build a prefix sum array where prefix[i] stores the number of valid words from index 0 to i. For a query [l, r], compute the result as prefix[r] - prefix[l - 1] (handle the edge case when l = 0). This converts repeated range counting into constant-time arithmetic. The preprocessing pass is linear, and every query is answered in O(1).
Character checks rely on simple string indexing, making the preprocessing pass extremely cheap. The prefix array effectively stores cumulative counts so the algorithm never scans the same range twice.
Recommended for interviews: Start by explaining the direct iteration method to demonstrate you understand the problem constraints. Then optimize with a prefix sum array to reduce repeated work. Interviewers usually expect the prefix sum approach because it converts range counting queries from O(n) per query to O(1) per query after linear preprocessing.
This approach processes each query independently by iterating through the specified range of the words list, checking if each word both starts and ends with a vowel. This is a straightforward approach with a complexity that depends on both the number of queries and the length of the ranges.
In C, we define a helper function is_vowel to check for vowels. The main function vowelStringsQueries iterates over each query, checks the specified range, and counts valid words using the helper function count_vowel_strings. The results are stored and returned in an integer array.
Time Complexity: O(Q * L), where Q is the number of queries and L is the average number of words per query range.
Space Complexity: O(1), aside from the result array space.
This approach seeks to improve efficiency by using a prefix sum array. In this approach, we first preprocess the words list to compute an array that stores the cumulative count of valid words up to each index. With this preprocessed information, each query can be answered in constant time.
In C, we first construct a prefix sum array that stores the cumulative count of valid words. Each query consists of quickly subtracting prefix sums to determine the number of valid words within the desired range, minimizing redundant calculations.
Time Complexity: O(W + Q), where W is the number of words and Q is the number of queries.
Space Complexity: O(W) for storing the prefix sum.
We can preprocess all the indices of the strings that start and end with a vowel, and record them in order in the array nums.
Next, we iterate through each query (l, r), and use binary search to find the first index i in nums that is greater than or equal to l, and the first index j that is greater than r. Therefore, the answer to the current query is j - i.
The time complexity is O(n + m times log n), and the space complexity is O(n). Where n and m are the lengths of the arrays words and queries, respectively.
Python
Java
C++
Go
TypeScript
We can create a prefix sum array s of length n+1, where s[i] represents the number of strings that start and end with a vowel in the first i strings of the array words. Initially, s[0] = 0.
Next, we iterate through the array words. If the current string starts and ends with a vowel, then s[i+1] = s[i] + 1, otherwise s[i+1] = s[i].
Finally, we iterate through each query (l, r). Therefore, the answer to the current query is s[r+1] - s[l].
The time complexity is O(n + m), and the space complexity is O(n). Where n and m are the lengths of the arrays words and queries, respectively.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Direct Iteration for Each Query | Time Complexity: O(Q * L), where Q is the number of queries and L is the average number of words per query range. |
| Prefix Sum Array | Time Complexity: O(W + Q), where W is the number of words and Q is the number of queries. |
| Preprocessing + Binary Search | — |
| Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Iteration for Each Query | O(n * q) | O(1) | Small input sizes or when query count is very low |
| Prefix Sum Array | O(n + q) | O(n) | Large number of range queries where repeated counting would be expensive |
Count Vowel Strings in Ranges - Leetcode 2559 - Python • NeetCodeIO • 9,287 views views
Watch 9 more video solutions →Practice Count Vowel Strings in Ranges with our built-in code editor and test cases.
Practice on FleetCode