Count Vowel Strings in Ranges

Problem Statement

In this problem, you are provided with an array of strings named words and a two-dimensional integer array queries. Each element of queries, denoted as queries[i] = [li, ri], requests you to determine how many strings within the subarray of words from index li to ri (inclusive) both commence and conclude with a vowel. The definition of vowels for this problem includes the characters 'a', 'e', 'i', 'o', and 'u'.

The objective is to compute the results for all these subarray queries and return them in an array ans, where each element ans[i] corresponds to the result of the i-th query in queries.

Examples

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 <= 105
• 1 <= words[i].length <= 40
• words[i] consists only of lowercase English letters.
• sum(words[i].length) <= 3 * 105
• 1 <= queries.length <= 105
• 0 <= li <= ri < words.length

Approach and Intuition

To efficiently approach the given problem, follow these significant steps:

1. Preprocess the List:

   • Iterate through the array words to check each string:
   • For each string, evaluate if it begins and ends with a vowel.
   • Create a boolean array vowelStartEnd where each index i carries True or False based on whether the corresponding index in words starts and ends with a vowel.

2. Efficient Query Handling:

   • Given the potential size of the queries and words list, evaluating each query directly from the words list might be inefficient.
   • Utilize a cumulative sum technique on the vowelStartEnd. This involves creating a prefix sum array that holds the count of True values up to every index i.
   • For each query [li, ri], retrieve the count of True in the vowelStartEnd between these indices using the prefix sum array.

3. Resolve Queries:

   • When resolving the queries, if li is 0, the result is directly the value at ri in the prefix sum array.
   • If li > 0, calculate the sum by subtracting the value at li-1 from the value at ri in the prefix sum array.
   • Populate each result into the results array ans corresponding to each query.

This approach ensures that you only preprocess the data once, and each query is resolved in constant time, which is efficient given the constraints. The preprocessing involves linear time complexity, and each query resolution is constant, yielding overall efficient time complexity for large inputs.

Solutions

class Solution {
public:
    vector<int> processWords(vector<string>& tokens,
                             vector<vector<int>>& requests) {
        vector<int> result(requests.size());
        unordered_set<char> vowelSet{'a', 'e', 'i', 'o', 'u'};
        vector<int> cumSum(tokens.size());
        int total = 0;
        for (int j = 0; j < tokens.size(); j++) {
            string word = tokens[j];
            if (vowelSet.count(word.front()) && vowelSet.count(word.back())) {
                total++;
            }
            cumSum[j] = total;
        }
    
        for (int j = 0; j < requests.size(); j++) {
            vector<int> query = requests[j];
            result[j] =
                cumSum[query[1]] -
                (query[0] == 0 ? 0 : cumSum[query[0] - 1]);
        }
    
        return result;
    }
};