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.
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; }}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.