Skip to main content
Talentd

Count Vowel Strings in Ranges - Solution & Explanation

MediumArrayStringPrefix Sum22 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

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 find the number of strings present in the range li to ri (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.

Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.

 

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 Overview

Problem Overview: You receive an array of words and multiple queries. Each query asks how many words in a given index range start and end with a vowel (a, e, i, o, u). The task is to return the count for every query efficiently.

Approach 1: Direct Iteration for Each Query (Time: O(n * q), Space: O(1))

The most straightforward solution processes each query independently. For every query range [l, r], iterate through the words from index l to r. For each word, check whether the first and last characters belong to the vowel set. Increment a counter when the condition is satisfied. This method requires only constant extra memory and is simple to implement, but it becomes slow when the number of queries is large because the same indices may be scanned repeatedly.

Approach 2: Prefix Sum Array (Time: O(n + q), Space: O(n))

The optimized solution precomputes information so each query can be answered in constant time. First iterate through the array of words and create a binary array where 1 means the word starts and ends with a vowel and 0 otherwise. Then build a prefix sum array where prefix[i] stores the number of valid words from index 0 to i. For a query [l, r], compute the result as prefix[r] - prefix[l - 1] (handle the edge case when l = 0). This converts repeated range counting into constant-time arithmetic. The preprocessing pass is linear, and every query is answered in O(1).

Character checks rely on simple string indexing, making the preprocessing pass extremely cheap. The prefix array effectively stores cumulative counts so the algorithm never scans the same range twice.

Recommended for interviews: Start by explaining the direct iteration method to demonstrate you understand the problem constraints. Then optimize with a prefix sum array to reduce repeated work. Interviewers usually expect the prefix sum approach because it converts range counting queries from O(n) per query to O(1) per query after linear preprocessing.

Approach 1: Direct Iteration for Each Query

This approach processes each query independently by iterating through the specified range of the words list, checking if each word both starts and ends with a vowel. This is a straightforward approach with a complexity that depends on both the number of queries and the length of the ranges.

In C, we define a helper function is_vowel to check for vowels. The main function vowelStringsQueries iterates over each query, checks the specified range, and counts valid words using the helper function count_vowel_strings. The results are stored and returned in an integer array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(Q * L), where Q is the number of queries and L is the average number of words per query range.
Space Complexity: O(1), aside from the result array space.

Try this approach in the editor →

Approach 2: Prefix Sum Array

This approach seeks to improve efficiency by using a prefix sum array. In this approach, we first preprocess the words list to compute an array that stores the cumulative count of valid words up to each index. With this preprocessed information, each query can be answered in constant time.

In C, we first construct a prefix sum array that stores the cumulative count of valid words. Each query consists of quickly subtracting prefix sums to determine the number of valid words within the desired range, minimizing redundant calculations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(W + Q), where W is the number of words and Q is the number of queries.
Space Complexity: O(W) for storing the prefix sum.

Try this approach in the editor →

Approach 3: 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.

Next, we iterate through each query (l, r), and use binary search to find the first index i in nums that is greater than or equal to l, and the first index j that is greater than r. Therefore, the answer to the current query is j - i.

The time complexity is O(n + m times log n), and the space complexity is O(n). Where n and m are the lengths of the arrays words and queries, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: 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.

Next, we iterate through the array words. If the current string starts and ends with a vowel, then s[i+1] = s[i] + 1, otherwise s[i+1] = s[i].

Finally, we iterate through each query (l, r). Therefore, the answer to the current query is s[r+1] - s[l].

The time complexity is O(n + m), and the space complexity is O(n). Where n and m are the lengths of the arrays words and queries, respectively.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct Iteration for Each Query

Time Complexity: O(Q * L), where Q is the number of queries and L is the average number of words per query range.
Space Complexity: O(1), aside from the result array space.

Prefix Sum Array

Time Complexity: O(W + Q), where W is the number of words and Q is the number of queries.
Space Complexity: O(W) for storing the prefix sum.

Preprocessing + Binary Search—
Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Iteration for Each QueryO(n * q)O(1)Small input sizes or when query count is very low
Prefix Sum ArrayO(n + q)O(n)Large number of range queries where repeated counting would be expensive

Video Solution

Count Vowel Strings in Ranges - Leetcode 2559 - Python • NeetCodeIO • 9,479 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Vowel Strings in Ranges easy or hard?
The problem is rated Medium on LeetCode. The main challenge is recognizing that repeated range counting can be optimized using a prefix sum array. Once that insight is clear, the implementation is straightforward.
Count Vowel Strings in Ranges Python/Java solution
Most implementations follow the same logic across languages. Build a prefix sum array after checking each word's first and last characters. Python, Java, C++, and C implementations simply differ in syntax but maintain the same O(n + q) algorithm.
How to solve Count Vowel Strings in Ranges in O(n)?
Preprocess the words to create a prefix sum array that tracks how many words start and end with vowels up to each index. For a query range [l, r], compute the result as prefix[r] minus prefix[l-1]. This avoids scanning the range repeatedly and keeps each query O(1) after linear preprocessing.
What is the best approach for Count Vowel Strings in Ranges?
The prefix sum approach is the most efficient solution. Precompute whether each word starts and ends with a vowel, then build a prefix array of cumulative counts. Each query can then be answered in O(1) time using prefix subtraction, giving overall complexity O(n + q).
Is Count Vowel Strings in Ranges asked at Google/Amazon/Meta?
Range query problems using prefix sums appear frequently in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the core idea of preprocessing cumulative counts to answer queries efficiently is a common interview pattern.
What data structure is used in Count Vowel Strings in Ranges?
The key data structure is a prefix sum array built from the input array of words. Each position stores the cumulative count of words that begin and end with vowels. Basic string indexing is used to check the first and last characters.
What is the time complexity of Count Vowel Strings in Ranges?
The optimal prefix sum solution runs in O(n + q) time where n is the number of words and q is the number of queries. Building the prefix array takes O(n), and each query is answered in constant time. The brute force approach can degrade to O(n * q).

Ready to solve this problem?

Practice Count Vowel Strings in Ranges with our built-in code editor and test cases.

Practice on FleetCode
Previous

Jump Game VII