Count Vowel Strings in Ranges
MedPrompt
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 at the indices ranging from 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.length
Approaches
2 approaches with complexity analysis and trade-offs.
A much more efficient approach is to precompute the counts to answer range queries quickly. The problem of finding the number of items with a certain property in a range is a classic application of the prefix sum technique. We can first determine for each word if it's a "vowel string" (starts and ends with a vowel). Then, we can build a prefix sum array on top of this information. The prefix sum array, prefixCounts, will store at index i the cumulative count of vowel strings from the beginning of the words array up to index i-1. With this prefixCounts array, the answer to any query [l, r] can be found in constant time by calculating prefixCounts[r+1] - prefixCounts[l].
Algorithm
- Create a prefix sum array,
prefixCounts, of sizeN + 1, whereNis the length of thewordsarray. InitializeprefixCounts[0] = 0. - Create a helper function
isVowel(char c). - Iterate through the
wordsarray fromi = 0toN-1. - For each
word, check if it starts and ends with a vowel. - Calculate the value for the current position in the prefix sum array:
prefixCounts[i+1] = prefixCounts[i] + (1 if the word is a vowel string, else 0). - After this single pass, the
prefixCountsarray is fully populated.prefixCounts[k]now holds the count of vowel strings inwords[0...k-1]. - Initialize an answer array
ansof sizeQ, whereQis the number of queries. - Iterate through each query
[l, r]. - The number of vowel strings in the range
[l, r]is the total count up to indexrminus the total count up to indexl-1. This can be calculated in O(1) time asprefixCounts[r + 1] - prefixCounts[l]. - Store this result in the
ansarray. - Return
ans.
Walkthrough
This approach involves two main phases: precomputation and query processing.
In the precomputation phase, we iterate through the words array just once. We maintain a running count of vowel strings and store it in a prefixCounts array. prefixCounts[i+1] will store the total number of vowel strings found in the subarray words[0...i].
In the query processing phase, we can answer any range query [l, r] instantly. The count of vowel strings from index l to r is simply the total count up to r minus the total count up to l-1. Using our prefixCounts array, this translates to prefixCounts[r+1] - prefixCounts[l]. This decouples the query processing time from the size of the range, making it extremely fast.
class Solution { private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } public int[] vowelStrings(String[] words, int[][] queries) { int n = words.length; int[] prefixCounts = new int[n + 1]; // Build the prefix sum array for (int i = 0; i < n; i++) { String word = words[i]; int vowelFlag = 0; if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) { vowelFlag = 1; } prefixCounts[i + 1] = prefixCounts[i] + vowelFlag; } int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int l = queries[i][0]; int r = queries[i][1]; // The count for range [l, r] is count(0..r) - count(0..l-1) // which corresponds to prefixCounts[r+1] - prefixCounts[l] ans[i] = prefixCounts[r + 1] - prefixCounts[l]; } return ans; }}Complexity
Time
O(N + Q), where N is the number of words and Q is the number of queries. We perform one pass over the `words` array to build the prefix sum array (O(N)), and one pass over the `queries` array to compute the answers (O(Q)). Each query is answered in O(1) time. This is very efficient and well within the time limits.
Space
O(N), where N is the length of `words`. This is the auxiliary space required to store the prefix sum array.
Trade-offs
Pros
Highly efficient, with linear time complexity.
Answers each range query in constant time after the initial precomputation.
Cons
Requires extra space proportional to the number of words to store the prefix sum array.
The most straightforward approach is to handle each query independently. For every query [l, r], we can iterate through the words array from index l to r. In each iteration, we check if the current word starts and ends with a vowel. We maintain a counter for the current query, incrementing it whenever we find such a word. After checking all words in the range, the value of the counter is the answer for that query.
Algorithm
- Initialize an integer array
ansof sizequeries.lengthto store the results. - Create a helper function
isVowel(char c)which returnstrueifcis one of 'a', 'e', 'i', 'o', 'u', andfalseotherwise. - Iterate through each query
queries[i] = [l, r]. - For each query, initialize a counter
count = 0. - Start a nested loop that iterates through the
wordsarray from indexltor(inclusive). - For each
wordin this range, get its first characterfirstCharand last characterlastChar. - Use the
isVowelhelper function to check if bothfirstCharandlastCharare vowels. - If the condition is met, increment the
count. - After the inner loop completes, assign the final
counttoans[i]. - After iterating through all queries, return the
ansarray.
Walkthrough
This method directly translates the problem statement into code. It processes one query at a time. For a query [l, r], it sets up a loop from l to r and, for each word, performs a check. This check involves accessing the first and last characters of the string and verifying if they are vowels. While simple, this approach re-evaluates the same words if they appear in multiple query ranges, leading to significant performance issues with a large number of words and queries.
class Solution { private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } public int[] vowelStrings(String[] words, int[][] queries) { int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int l = queries[i][0]; int r = queries[i][1]; int count = 0; for (int j = l; j <= r; j++) { String word = words[j]; if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) { count++; } } ans[i] = count; } return ans; }}Complexity
Time
O(Q * N), where Q is the number of queries and N is the number of words. For each of the Q queries, we might iterate through up to N words in the worst case (e.g., a query `[0, N-1]`). This leads to a quadratic time complexity which is too slow for the given constraints.
Space
O(Q) to store the answer array. If the output array is not considered as extra space, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Requires minimal extra space (besides the output array).
Cons
Highly inefficient due to redundant computations for overlapping query ranges.
Fails to pass time limits on platforms like LeetCode for the given constraints.
Solutions
Solution
class Solution {private List<Integer> nums = new ArrayList<>();public int[] vowelStrings(String[] words, int[][] queries) { Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u'); for (int i = 0; i < words.length; ++i) { char a = words[i].charAt(0), b = words[i].charAt(words[i].length() - 1); if (vowels.contains(a) && vowels.contains(b)) { nums.add(i); } } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int l = queries[i][0], r = queries[i][1]; ans[i] = search(r + 1) - search(l); } return ans; }private int search(int x) { int l = 0, r = nums.size(); while (l < r) { int mid = (l + r) >> 1; if (nums.get(mid) >= x) { r = mid; } else { l = mid + 1; } } return l; }}class Solution {public: vector<int> vowelStrings(vector<string> &words, vector<vector<int>> &queries) { unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'}; vector<int> nums; for (int i = 0; i < words.size(); ++i) { char a = words[i][0], b = words[i].back(); if (vowels.count(a) && vowels.count(b)) { nums.push_back(i); } } vector<int> ans; for (auto &q : queries) { int l = q[0], r = q[1]; int cnt = upper_bound(nums.begin(), nums.end(), r) - lower_bound(nums.begin(), nums.end(), l); ans.push_back(cnt); } return ans; }};class Solution: def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]: vowels = set("aeiou") nums = [i for i, w in enumerate(words) if w[0] in vowels and w[- 1] in vowels] return [bisect_right(nums, r) - bisect_left(nums, l) for l, r in queries]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.