Count Vowel Strings in Ranges solution and explanation
IBM
Google
9 more videos on this problem
Count Vowel Strings in Ranges - Leetcode 2559 - PythonNeetCodeIO · 11:27 · 9K views
Count Vowel Strings in Ranges | Simple Thought Process | Leetcode 2559 | codestorywithMIKcodestorywithMIK · 15:57 · 8K views
Count Vowel Strings in Ranges | Leetcode 2559Techdose · 10:50 · 4K views
Leetcode 2559 Count Vowel Strings in Ranges (Java) - Leetcode Contest 331 - Beats 100%TheAnalyticGuy · 6:42 · 494 views
2559. Count Vowel Strings in Ranges (Leetcode Medium)Programming Live with Larry · 7:14 · 288 views
Leetcode 2559. Count Vowel Strings in RangesElite Code · 29:26 · 124 views
Leetcode 2559: Count Vowel Strings in Ranges | Coding Interview Solution with Prefix Sums #2559doiknowthisthing · 3:24 · 88 views
LeetCode Daily 02.01.2025 Task 2559 Count Vowel Strings in RangesEdTech · 27:22 · 67 views
Count Vowel Strings in Ranges - Leetcode 2559Code With K5KC · 7:50 · 48 views
Count Vowel Strings in Ranges - Python || O(n) solution || LeetCode Daily 2559codegrind · 7:03 · 36 views
The problem
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 <= 1051 <= words[i].length <= 40words[i]consists only of lowercase English letters.sum(words[i].length) <= 3 * 1051 <= queries.length <= 1050 <= 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.
def is_vowel(c):
return c in 'aeiou'
def count_vowel_strings_queries(words, queries):
results = []
for l, r in queries:
count = sum(1 for word in words[l:r+1] if is_vowel(word[0]) and is_vowel(word[-1]))
results.append(count)
return resultsimport java.util.List;
import java.util.ArrayList;
public class VowelStringCounter {
private boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public List<Integer> countVowelStringsQueries(String[] words, int[][] queries) {
List<Integer> result = new ArrayList<>();
for (int[] query : queries) {
int count = 0;
for (int i = query[0]; i <= query[1]; i++) {
String word = words[i];
if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) {
count++;
}
}
result.add(count);
}
return result;
}
}#include <iostream>
#include <vector>
#include <string>
#include <cctype>
bool isVowel(char c) {
c = std::tolower(c);
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int vowelStringsInRange(const std::vector<std::string>& words, int l, int r) {
int count = 0;
for (int i = l; i <= r; ++i) {
if (isVowel(words[i].front()) && isVowel(words[i].back())) {
++count;
}
}
return count;
}
std::vector<int> countVowelStringsQueries(std::vector<std::string>& words, std::vector<std::vector<int>>& queries) {
std::vector<int> result;
for (const auto& query : queries) {
result.push_back(vowelStringsInRange(words, query[0], query[1]));
}
return result;
}function isVowel(c) {
return 'aeiou'.includes(c);
}
function countVowelStringsQueries(words, queries) {
const results = [];
queries.forEach(query => {
let [l, r] = query;
let count = 0;
for (let i = l; i <= r; i++) {
if (isVowel(words[i][0]) && isVowel(words[i][words[i].length - 1])) {
count++;
}
}
results.push(count);
});
return results;
}#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool is_vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int count_vowel_strings(char **words, int wordsSize, int l, int r) {
int count = 0;
for (int i = l; i <= r; i++) {
int len = strlen(words[i]);
if (is_vowel(words[i][0]) && is_vowel(words[i][len - 1])) {
count++;
}
}
return count;
}
int* vowelStringsQueries(char **words, int wordsSize, int** queries, int queriesSize, int* ansSize) {
int* ans = (int*)malloc(sizeof(int) * queriesSize);
*ansSize = queriesSize;
for (int i = 0; i < queriesSize; i++) {
int l = queries[i][0];
int r = queries[i][1];
ans[i] = count_vowel_strings(words, wordsSize, l, r);
}
return ans;
}using System;
using System.Collections.Generic;
class VowelStringCounter {
private static bool IsVowel(char c) {
return "aeiou".IndexOf(c) >= 0;
}
public List<int> CountVowelStringsQueries(string[] words, int[][] queries) {
var results = new List<int>();
foreach (var query in queries) {
int count = 0;
for (int i = query[0]; i <= query[1]; i++) {
var word = words[i];
if (IsVowel(word[0]) && IsVowel(word[^1])) {
count++;
}
}
results.Add(count);
}
return results;
}
}This Python solution simply uses a generator expression to count words that meet the vowel criteria within each query range, accumulating the results in a list to be returned. The use of the is_vowel function helps keep the checks concise.
Time Complexity: O(Q * L)
Space Complexity: O(Q) for the accumulated results.
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.
def is_vowel(c):
return c in 'aeiou'
def build_prefix_sum(words):
prefix = [0] * len(words)
prefix[0] = 1 if is_vowel(words[0][0]) and is_vowel(words[0][-1]) else 0
for i in range(1, len(words)):
prefix[i] = prefix[i - 1] + (1 if is_vowel(words[i][0]) and is_vowel(words[i][-1]) else 0)
return prefix
def count_vowel_strings_queries(words, queries):
prefix = build_prefix_sum(words)
results = []
for l, r in queries:
count = prefix[r] - (prefix[l - 1] if l > 0 else 0)
results.append(count)
return resultsimport java.util.List;
import java.util.ArrayList;
public class VowelStringCounter {
private boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public List<Integer> countVowelStringsQueries(String[] words, int[][] queries) {
int n = words.length;
int[] prefix = new int[n];
prefix[0] = isVowel(words[0].charAt(0)) && isVowel(words[0].charAt(words[0].length() - 1)) ? 1 : 0;
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + (isVowel(words[i].charAt(0)) && isVowel(words[i].charAt(words[i].length() - 1)) ? 1 : 0);
}
List<Integer> result = new ArrayList<>();
for (int[] query : queries) {
int l = query[0];
int r = query[1];
result.add(l > 0 ? prefix[r] - prefix[l - 1] : prefix[r]);
}
return result;
}
}#include <iostream>
#include <vector>
#include <string>
bool isVowel(char c) {
return "aeiou".find(c) != std::string::npos;
}
std::vector<int> prefixSums(const std::vector<std::string>& words) {
std::vector<int> prefix(words.size(), 0);
prefix[0] = isVowel(words[0].front()) && isVowel(words[0].back()) ? 1 : 0;
for (size_t i = 1; i < words.size(); ++i) {
prefix[i] = prefix[i - 1] + (isVowel(words[i].front()) && isVowel(words[i].back()) ? 1 : 0);
}
return prefix;
}
std::vector<int> countVowelStringsQueries(std::vector<std::string>& words, std::vector<std::vector<int>>& queries) {
std::vector<int> prefix = prefixSums(words);
std::vector<int> result;
for (const auto& query : queries) {
int l = query[0], r = query[1];
int count = l > 0 ? prefix[r] - prefix[l - 1] : prefix[r];
result.push_back(count);
}
return result;
}function isVowel(c) {
return 'aeiou'.includes(c);
}
function buildPrefixSum(words) {
const prefix = new Array(words.length).fill(0);
prefix[0] = isVowel(words[0][0]) && isVowel(words[0][words[0].length - 1]) ? 1 : 0;
for (let i = 1; i < words.length; i++) {
prefix[i] = prefix[i - 1] + (isVowel(words[i][0]) && isVowel(words[i][words[i].length - 1]) ? 1 : 0);
}
return prefix;
}
function countVowelStringsQueries(words, queries) {
const prefix = buildPrefixSum(words);
const results = [];
queries.forEach(([l, r]) => {
const count = l > 0 ? prefix[r] - prefix[l - 1] : prefix[r];
results.push(count);
});
return results;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
bool is_vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
void build_prefix_sum(char **words, int wordsSize, int* prefix) {
prefix[0] = (is_vowel(words[0][0]) && is_vowel(words[0][strlen(words[0]) - 1])) ? 1 : 0;
for (int i = 1; i < wordsSize; i++) {
prefix[i] = prefix[i - 1] + ((is_vowel(words[i][0]) && is_vowel(words[i][strlen(words[i]) - 1])) ? 1 : 0);
}
}
int* vowelStringsQueries(char **words, int wordsSize, int** queries, int queriesSize, int* ansSize) {
int* ans = (int*)malloc(sizeof(int) * queriesSize);
int* prefix = (int*)calloc(wordsSize, sizeof(int));
build_prefix_sum(words, wordsSize, prefix);
*ansSize = queriesSize;
for (int i = 0; i < queriesSize; i++) {
int l = queries[i][0];
int r = queries[i][1];
ans[i] = (l > 0) ? prefix[r] - prefix[l - 1] : prefix[r];
}
free(prefix);
return ans;
}using System;
using System.Collections.Generic;
class VowelStringCounter {
private bool IsVowel(char c) {
return "aeiou".IndexOf(c) >= 0;
}
private int[] BuildPrefixSum(string[] words) {
int n = words.Length;
int[] prefix = new int[n];
prefix[0] = IsVowel(words[0][0]) && IsVowel(words[0][^1]) ? 1 : 0;
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + (IsVowel(words[i][0]) && IsVowel(words[i][^1]) ? 1 : 0);
}
return prefix;
}
public List<int> CountVowelStringsQueries(string[] words, int[][] queries) {
int[] prefix = BuildPrefixSum(words);
var results = new List<int>();
foreach (var query in queries) {
int l = query[0];
int r = query[1];
results.Add(l > 0 ? prefix[r] - prefix[l - 1] : prefix[r]);
}
return results;
}
}Python constructs the prefix sum to track how many valid words are present at each index inclusively from the start of the list. This preprocessing enables each query to be answered efficiently by subtracting the cumulative counts within the specified range.
Time Complexity: O(W + Q)
Space Complexity: O(W) owing to the prefix storage.
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.
function vowelStrings(words: string[], queries: number[][]): number[] {
const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
const nums: number[] = [];
for (let i = 0; i < words.length; ++i) {
if (vowels.has(words[i][0]) && vowels.has(words[i][words[i].length - 1])) {
nums.push(i);
}
}
const search = (x: number): number => {
let l = 0,
r = nums.length;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
return queries.map(([l, r]) => search(r + 1) - search(l));
}func vowelStrings(words []string, queries [][]int) []int {
vowels := map[byte]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
nums := []int{}
for i, w := range words {
if vowels[w[0]] && vowels[w[len(w)-1]] {
nums = append(nums, i)
}
}
ans := make([]int, len(queries))
for i, q := range queries {
l, r := q[0], q[1]
ans[i] = sort.SearchInts(nums, r+1) - sort.SearchInts(nums, l)
}
return ans
}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.
function vowelStrings(words: string[], queries: number[][]): number[] {
const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
const s = new Array(words.length + 1).fill(0);
words.forEach((w, i) => {
const x = +(vowels.has(w[0]) && vowels.has(w.at(-1)!));
s[i + 1] = s[i] + x;
});
return queries.map(([l, r]) => s[r + 1] - s[l]);
}func vowelStrings(words []string, queries [][]int) []int {
vowels := map[byte]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
n := len(words)
s := make([]int, n+1)
for i, w := range words {
x := 0
if vowels[w[0]] && vowels[w[len(w)-1]] {
x = 1
}
s[i+1] = s[i] + x
}
ans := make([]int, len(queries))
for i, q := range queries {
l, r := q[0], q[1]
ans[i] = s[r+1] - s[l]
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Direct Iteration for Each Query | Time Complexity: O(Q * L) |
| Prefix Sum Array | Time Complexity: O(W + Q) |
| Preprocessing + Binary Search | – |
| Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Iteration for Each Query | O(n * q) | O(1) | Small input sizes or when query count is very low |
| Prefix Sum Array | O(n + q) | O(n) | Large number of range queries where repeated counting would be expensive |
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).