#2559

Medium

LeetCode Problem Workspace

Count Vowel Strings in Ranges

Count the number of strings that start and end with a vowel in given ranges within an array of words.

Problem Statement

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 count how many words in the subarray from indices li to ri (both inclusive) start and end with a vowel.

Return an array, ans, where ans[i] is the answer to the ith query. Efficiently compute the answer by precomputing data that allows constant-time querying.

Examples

Example 1

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]

Output: [2,3,0]

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]

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

Solution Approach

Precompute Prefix Sum

First, iterate through the words array and create a boolean array that marks whether each word starts and ends with a vowel. Then, build a prefix sum array where each element at index i represents the count of valid words up to index i in the words array.

Query Answering

For each query, simply calculate the number of valid words in the given range using the prefix sum array. The result for a query [li, ri] is the difference between the prefix sum at ri and li-1, which can be computed in constant time.

Edge Case Handling

Handle edge cases such as empty ranges or words that do not start or end with a vowel. Ensure the prefix sum array is initialized correctly and includes all necessary boundary conditions.

Complexity Analysis

Metric	Value
Time	O(M + N)
Space	O(M)

The time complexity for preprocessing is O(M), where M is the total number of characters in all words. Answering each query takes O(1) time due to the prefix sum array. Therefore, the overall time complexity is O(M + N), where N is the number of queries. The space complexity is O(M) for storing the prefix sum and vowel-check arrays.

What Interviewers Usually Probe

Candidate is able to implement the prefix sum approach to optimize range queries.
Candidate correctly handles the constraints and performs preprocessing efficiently.
Candidate understands the concept of vowel-checking and its application in this problem.

Common Pitfalls or Variants

Common pitfalls

Failing to initialize the prefix sum array correctly, especially with respect to boundary conditions.
Not efficiently checking whether a word starts and ends with a vowel, resulting in unnecessary time complexity.
Misunderstanding the problem constraints and attempting to solve it with a brute-force approach, leading to time limit exceeded errors.

Follow-up variants

Instead of counting words starting and ending with vowels, count words starting with a vowel but ending with a consonant.
Given a range, find the longest valid word within it that starts and ends with a vowel.
Modify the problem to count strings containing vowels at any positions within the given ranges.

FAQ

What is the optimal solution for 'Count Vowel Strings in Ranges'?

The optimal solution involves precomputing a prefix sum of words that start and end with vowels, which allows answering each query in constant time.

How do I approach range queries in this problem?

Use a prefix sum approach where each entry contains the count of words that meet the condition up to that index. Subtract values from the prefix sum array to answer range queries efficiently.

What should I focus on for the 'Array plus String' pattern?

Focus on efficiently managing string checks and optimizing range queries using array-based techniques like prefix sums.

How does the vowel-checking condition affect the solution?

By precomputing a binary array that marks words starting and ending with vowels, we can quickly compute the answer for any query range.

What are common mistakes to avoid in this problem?

Avoid inefficient brute-force solutions, incorrect handling of the prefix sum array, and errors in checking the vowel conditions for each word.

terminal

Solution

Solution 1: Preprocessing + Binary Search

We can preprocess all the indices of the strings that start and end with a vowel, and record them in order in the array $nums$.

1

2

3

4

5

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = set("aeiou")
        nums = [i for i, w in enumerate(words) if w[0] in vowels and w[-1] in vowels]
        return [bisect_right(nums, r) - bisect_left(nums, l) for l, r in queries]

Solution 2: Prefix Sum

We can create a prefix sum array $s$ of length $n+1$, where $s[i]$ represents the number of strings that start and end with a vowel in the first $i$ strings of the array $words$. Initially, $s[0] = 0$.

1

2

3

4

5

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = set("aeiou")
        nums = [i for i, w in enumerate(words) if w[0] in vowels and w[-1] in vowels]
        return [bisect_right(nums, r) - bisect_left(nums, l) for l, r in queries]

Continue Practicing

#2391 minimum amount of time to collect garbage #2381 shifting letters ii #2055 plates between candles