Count Vowel Strings in Ranges

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

1. Create a prefix sum array, prefixCounts, of size N + 1, where N is the length of the words array. Initialize prefixCounts[0] = 0.
2. Create a helper function isVowel(char c).
3. Iterate through the words array from i = 0 to N-1.
4. For each word, check if it starts and ends with a vowel.
5. 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).
6. After this single pass, the prefixCounts array is fully populated. prefixCounts[k] now holds the count of vowel strings in words[0...k-1].
7. Initialize an answer array ans of size Q, where Q is the number of queries.
8. Iterate through each query [l, r].
9. The number of vowel strings in the range [l, r] is the total count up to index r minus the total count up to index l-1. This can be calculated in O(1) time as prefixCounts[r + 1] - prefixCounts[l].
10. Store this result in the ans array.
11. Return ans.

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