Count Vowel Strings in Ranges

Problem Description

You are 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 present at the indices ranging from l_i to r_i (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.

Key Insights

• A string starts and ends with a vowel if both its first and last characters are in the set of vowels {'a', 'e', 'i', 'o', 'u'}.
• We can preprocess the words array to create a prefix sum array to quickly answer the range queries.
• The prefix sum array allows us to compute the number of valid strings in any range in constant time.

Space and Time Complexity

Time Complexity: O(n + q), where n is the number of words and q is the number of queries. Space Complexity: O(n), for the prefix sum array.

Solution

To solve the problem, we can use a two-step approach:

1. Create a prefix sum array where each entry at index i holds the count of strings from the beginning of the words array to index i that start and end with a vowel.
2. For each query, calculate the result using the prefix sum array by subtracting the relevant counts, allowing us to efficiently answer each query in constant time.

Code Solutions