1871. Count Vowel Strings in Ranges
Problem Description
Given a 0-indexed array of strings words and a 2D array of integers queries, each query queries[i] = [l_i, r_i] asks us to find the number of strings in the range [l_i, r_i] (inclusive) that start and end with a vowel. The vowels are 'a', 'e', 'i', 'o', and 'u'. Return an array ans of size queries.length, where ans[i] is the answer to the ith query.
Example:
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").
The answer to the query [1,4] is 3 (strings "ece", "aa", "e").
The answer to the query [1,1] is 0.
We return [2,3,0].
Solution Code
class Solution {
public int[] vowelStrings(String[] words, int[][] queries) {
// Precompute the prefix sum array
int n = words.length;
int[] prefixSum = new int[n + 1];
// Set of vowels for quick lookup
Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
// Compute prefix sum
for (int i = 0; i < n; i++) {
String word = words[i];
boolean startsWithVowel = vowels.contains(word.charAt(0));
boolean endsWithVowel = vowels.contains(word.charAt(word.length() - 1));
prefixSum[i + 1] = prefixSum[i] + (startsWithVowel && endsWithVowel ? 1 : 0);
}
// Process 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];
ans[i] = prefixSum[r + 1] - prefixSum[l];
}
return ans;
}
}
Approach Name
Prefix Sum Approach
Intuition
The problem requires us to answer multiple range queries efficiently. To do this, we can precompute a prefix sum array where each entry at index i represents the number of strings in words[0..i-1] that start and end with a vowel. This allows us to answer each query in constant time by subtracting the prefix sum at the start of the range from the prefix sum at the end of the range.
Algorithm
- Precompute Prefix Sum:
- Initialize a prefix sum array
prefixSumof sizen + 1, wherenis the number of words. - Iterate through each word in
words:- Check if the word starts and ends with a vowel.
- Update the prefix sum array accordingly.
- Initialize a prefix sum array
- Process Queries:
- For each query
[l, r], compute the result asprefixSum[r + 1] - prefixSum[l]. - Store the result in the answer array
ans.
- For each query
- Return the Answer:
- Return the array
anscontaining the results for all queries.
- Return the array
Complexity Analysis
- Time Complexity: O(n + q), where
nis the number of words andqis the number of queries. We traverse the words once to compute the prefix sum and then process each query in constant time. - Space Complexity: O(n), for storing the prefix sum array.