Count Vowel Strings in Ranges Solution In C++/Java/Python/JS
Problem Description
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 at the indices ranging from 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
We are given a 2D queries array where each query specifies a range [l, r] (inclusive). For each query, we need to count how many strings in the words array start and end with a vowel and have an index within the specified range. These strings are referred to as "vowel strings." In other words, for each query, we need to count the number of vowel strings within the subarray words[l:r]. Let’s explore!
Brute Force Approach
Intuition
To solve the problem using a brute-force method, we handle each query independently by directly inspecting the words in the specified range. The key idea is simple: for each query [l, r], we loop from index l to r and check whether each word in that range starts and ends with a vowel.
Since we’re not doing any preprocessing, every query requires scanning its full range again, even if overlapping with previous queries. This makes the approach easy to implement but inefficient for large inputs or many queries.
This brute-force technique is ideal for small datasets or for verifying correctness before optimizing. However, it doesn't scale well for high-performance needs.
Approach
Step 1: Understand the Query Requirements
Each query provides a range [l, r], and asks us to count how many strings within that range start and end with a vowel. Since there's no preprocessing involved, we must answer each query independently by checking all elements within the given range.
Step 2: Define a Vowel Checker
We create a helper function isVowel(char ch) to determine whether a given character is a vowel. This function checks if the character is one of 'a', 'e', 'i', 'o', or 'u'. This ensures we can easily check both the first and last character of any string.
Step 3: Process Each Query Separately
or every query in the input:
- Extract the start and end indices l and r.
- Initialize a counter to 0.
- Loop through all indices i from l to r.
Step 4: Check Each Word in Range
For each index i in the current query range:
- Get the word at words[i].
- Check if its first character and last character are both vowels using the helper function.
- If both are vowels, increment the counter.
Step 5: Store and Return Results
After processing each query:
- Add the final count for that query to a results list.
- Once all queries are processed, return the results list containing the answer for each one.
Dry Run
Input: words = ["aba", "bcb", "ece", "aa", "e"]
queries = [[0, 2], [1, 4], [1, 1]]
We need to count how many strings in each query range [l, r] start and end with a vowel.
Vowels = {'a', 'e', 'i', 'o', 'u'}
Query 1: [0, 2] → words[0] to words[2]
- words[0] = "aba" → starts with 'a' and ends with 'a' → count = 1
- words[1] = "bcb" → starts with 'b' → not a vowel → skip
- words[2] = "ece" → starts with 'e' and ends with 'e' → count = 2
Result for this query: 2
Query 2: [1, 4] → words[1] to words[4]
- words[1] = "bcb" → not a vowel string → skip
- words[2] = "ece" → vowel string → count = 1
- words[3] = "aa" → vowel string → count = 2
- words[4] = "e" → vowel string → count = 3
Result for this query: 3
Query 3: [1, 1] → words[1] only
- words[1] = "bcb" → not a vowel string → count = 0
Result for this query: 0
Final Output : [2,3,0]
Code for All Languages
C++
// Approach: Brute-Force Range Check for Vowel Strings
// Language: C++
class Solution {
public:
// Helper function to check if a character is a vowel
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
// This function processes multiple queries, where each query asks
// for the number of strings that start and end with a vowel in a given range.
vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
vector<int> result;
// Step 1: Process each query one by one
for (const auto& query : queries) {
int l = query[0]; // start index of the range
int r = query[1]; // end index of the range
int count = 0;
// Step 2: Iterate over the range [l, r]
for (int i = l; i <= r; ++i) {
const string& word = words[i];
// Step 3: Check if the word starts and ends with a vowel
if (isVowel(word.front()) && isVowel(word.back())) {
count++;
}
}
// Step 4: Store the result for the current query
result.push_back(count);
}
// Step 5: Return the result for all queries
return result;
}
};Java
// Approach: Brute-Force Range Check for Vowel Strings
// Language: Java
class Solution {
// Helper method to check if a character is a vowel
private boolean isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
// This method processes multiple queries. Each query asks how many words
// in a given index range start and end with a vowel.
public int[] vowelStrings(String[] words, int[][] queries) {
int[] result = new int[queries.length];
// Step 1: Process each query one by one
for (int q = 0; q < queries.length; q++) {
int l = queries[q][0]; // start index of the range
int r = queries[q][1]; // end index of the range
int count = 0;
// Step 2: Iterate over the range [l, r]
for (int i = l; i <= r; i++) {
String word = words[i];
// Step 3: Check if the word starts and ends with a vowel
if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) {
count++;
}
}
// Step 4: Store the result for the current query
result[q] = count;
}
// Step 5: Return the result array
return result;
}
}Python
# Approach: Brute-Force Range Check for Vowel Strings
# Language: Python
class Solution(object):
def vowelStrings(self, words, queries):
"""
:type words: List[str]
:type queries: List[List[int]]
:rtype: List[int]
"""
# Helper function to check if a character is a vowel
def is_vowel(ch):
return ch in {'a', 'e', 'i', 'o', 'u'}
result = []
# Step 1: Process each query one by one
for query in queries:
l, r = query[0], query[1] # Start and end indices of the range
count = 0
# Step 2: Iterate over the range [l, r]
for i in range(l, r + 1):
word = words[i]
# Step 3: Check if the word starts and ends with a vowel
if is_vowel(word[0]) and is_vowel(word[-1]):
count += 1
# Step 4: Store the result for the current query
result.append(count)
# Step 5: Return the final list of results
return resultJavascript
// Approach: Brute-Force Range Check for Vowel Strings
// Language: JavaScript
/**
* @param {string[]} words - Array of lowercase words
* @param {number[][]} queries - Each query is [l, r] asking for words from index l to r
* @return {number[]} - Array containing the answer to each query
*/
var vowelStrings = function(words, queries) {
const result = [];
// Helper function to check if a character is a vowel
const isVowel = (ch) => {
return ch === 'a' || ch === 'e' || ch === 'i' || ch === 'o' || ch === 'u';
};
// Step 1: Process each query one by one
for (let q = 0; q < queries.length; q++) {
const [l, r] = queries[q]; // Start and end indices of the range
let count = 0;
// Step 2: Iterate over the range [l, r]
for (let i = l; i <= r; i++) {
const word = words[i];
// Step 3: Check if the word starts and ends with a vowel
if (isVowel(word[0]) && isVowel(word[word.length - 1])) {
count++;
}
}
// Step 4: Store the result for the current query
result.push(count);
}
// Step 5: Return the final list of results
return result;
};Time Complexity: O(m × q)
- Processing Queries (Outer Loop)
—We process each of the q queries individually.
— Each query contains a range [l, r] to evaluate.
— So we iterate through all queries: O(q), where q is the number of queries. - Scanning Ranges (Inner Loop)
— For each query [l, r], we iterate over the subarray from index l to r.
— In the worst case, the range could cover the entire array, meaning up to m iterations, where m is the length of words.
— So, for q queries with ranges of size up to m, total worst-case iterations: O(m × q). - Vowel Check Per Word
— For each word within a range, we check its first and last characters: O(1) time per word.
— These are constant time operations and do not depend on the word’s length. - Overall Time Complexity
Total Time: O(m × q), where m is the number of words and q is the number of queries.
Space Complexity: O(q)
- Auxiliary Space Complexity: O(1)
— No extra data structures are used for vowel checking. The check is done inline using simple conditionals: O(1)
— Variables like l, r, count, and loop indices use constant space: O(1) - Total Space Complexity
—Stores the answer for each of the q queries: O(q)
Why the Brute-Force Approach Gives TLE
The brute-force solution checks each word for every query by iterating over the range [l, r]. With up to 10⁵ queries and each range potentially spanning up to 10⁵ words, the total operations can reach 10¹⁰ in the worst case. Since each operation involves string access and character comparison, this exceeds the time limits for competitive environments, leading to TLE (Time Limit Exceeded).
So now, we’re thinking smarter: Instead of checking every word for every query, which repeats the same work, we preprocess the data once using a prefix sum array. This way, we can instantly know how many vowel-strings exist in any range just by subtracting two values. It’s like turning a time-consuming manual count into a quick lookup — much faster, much cleaner, and perfect for handling large input sizes.
Optimal Approach
Intuition
In a brute-force solution, we would handle each query by looping through the words between indices l and r and counting how many of them start and end with vowels. To check this quickly, we could use a set of vowels (a, e, i, o, u) and test each word’s first and last character. This part is efficient per word, but doing this check again and again for every query becomes costly — especially when queries have wide ranges or there are many queries overall.
The main issue here is repetition. Many queries overlap, which means the same word might be checked multiple times unnecessarily. This leads to a lot of wasted work.
To fix this, we use a smarter strategy: prefix sums. First, we scan through the list of words once and build an array that keeps a running total of vowel-words seen so far. For example, if the 3rd word is a vowel-word, then prefixSum[3] will tell us how many vowel-words we’ve seen up to that point.
With this prefix sum array ready, we can now answer any query in constant time. To find the number of vowel-words between index l and r, we simply compute:
prefixSum[r + 1] - prefixSum[l]
Why r + 1? Because we build our prefix sum with an extra 0 at the start (prefixSum[0] = 0), so that each value at i+1 stores the count for the first i words. This way, subtracting prefixSum[l] removes all words before l, and we’re left with just the count from l to r.
Example:
Say our prefix sum array is: [0, 1, 2, 2, 3, 3, 4]
For query [1, 5], we do: prefixSum[6] - prefixSum[1] = 4 - 1 = 3
This tells us that there are 3 vowel-words in that range, without checking each one manually.
By turning repeated work into a one-time setup, this prefix sum method gives us huge performance gains and handles large inputs with ease.
Approach
Step 1: Define a Helper to Check Vowel Strings
We first define a small utility function to check if a word starts and ends with a vowel. This is done by checking whether both the first and last characters belong to a set of vowels (a, e, i, o, u). This check takes constant time, O(1), for each word.
Step 2: Build a Prefix Sum Array
We initialize a prefix sum array of size n + 1 (where n is the number of words). This array stores, at each position i, the total number of vowel-strings from index 0 to i - 1 in the original words list.
For each word:
- If it is a vowel-string, increment the cumulative count.
- Copy the cumulative count to the current prefixSum position.
This prefix sum array allows us to precompute and store the cumulative number of vowel-strings in a single pass.
Step 3: Answer Each Query in Constant Time
For each query [l, r], we compute the number of vowel-strings in the range by subtracting:
prefixSum[r + 1] - prefixSum[l]
This subtraction gives us the number of vowel-strings between l and r (both inclusive) by removing the count before index l.
Step 4: Store and Return the Results
We create an output list ans where for each query we store the result calculated in Step 3. Once all queries are processed, we return this list.
Dry Run
input : words = ["aba", "bcb", "ece", "aa", "e"]
queries = [[0, 2], [1, 4], [1, 1]]
Step 1: Identify valid vowel strings
- We check if each word starts and ends with a vowel:
"aba" → starts with 'a', ends with 'a' → valid
"bcb" → starts with 'b', ends with 'b' → not valid
"ece" → starts with 'e', ends with 'e' → valid
"aa" → starts with 'a', ends with 'a' → valid
"e" → starts with 'e', ends with 'e' → valid
So valid vowel strings are at indices: 0, 2, 3, 4
Step 2: Build prefix sum array
We create a prefix sum array of size (words.length + 1)
prefixSum[0] = 0
prefixSum[1] = prefixSum[0] + 1 = 1 (aba is valid)
prefixSum[2] = prefixSum[1] + 0 = 1 (bcb is not valid)
prefixSum[3] = prefixSum[2] + 1 = 2 (ece is valid)
prefixSum[4] = prefixSum[3] + 1 = 3 (aa is valid)
prefixSum[5] = prefixSum[4] + 1 = 4 (e is valid)
Final prefixSum = [0, 1, 1, 2, 3, 4]
Step 3: Answer the queries
Query [0, 2]:
Result = prefixSum[3] - prefixSum[0] = 2 - 0 = 2
Query [1, 4]:
Result = prefixSum[5] - prefixSum[1] = 4 - 1 = 3
Query [1, 1]:
Result = prefixSum[2] - prefixSum[1] = 1 - 1 = 0
Final Output: [2, 3, 0]
Code for All Languages
C++
// Approach: Prefix Sum Optimization
// Language: C++
class Solution {
public:
// Utility function to check if a character is a vowel
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
// Main function to solve the problem
vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
int n = words.size();
vector<int> prefixSum(n + 1, 0); // Prefix sum array of size n + 1
// Step 1: Build the prefix sum array
for (int i = 0; i < n; ++i) {
// Carry forward the previous sum
prefixSum[i + 1] = prefixSum[i];
// If the current word starts and ends with a vowel, increment the sum
if (isVowel(words[i][0]) && isVowel(words[i].back())) {
prefixSum[i + 1]++;
}
}
// Step 2: Answer each query in constant time
vector<int> result;
for (const auto& query : queries) {
int l = query[0];
int r = query[1];
// Use the prefix sum difference to get the count in range [l, r]
result.push_back(prefixSum[r + 1] - prefixSum[l]);
}
// Step 3: Return the results for all queries
return result;
}
};Java
// Approach: Prefix Sum Optimization
// Language: Java
class Solution {
// Helper method to check if a character is a vowel
private boolean isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
// Main method to solve the problem
public int[] vowelStrings(String[] words, int[][] queries) {
int n = words.length;
int[] prefixSum = new int[n + 1]; // Prefix sum array of size n+1
// Step 1: Build the prefix sum array
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i]; // Carry forward previous sum
// If the word starts and ends with a vowel, increment the sum
if (isVowel(words[i].charAt(0)) && isVowel(words[i].charAt(words[i].length() - 1))) {
prefixSum[i + 1]++;
}
}
// Step 2: Answer each query in constant time using prefix sum difference
int[] result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int l = queries[i][0];
int r = queries[i][1];
result[i] = prefixSum[r + 1] - prefixSum[l];
}
// Step 3: Return the result array containing answers for all queries
return result;
}
}Python
# Approach: Prefix Sum Optimization
# Language: Python
class Solution(object):
def is_vowel(self, ch):
"""
Helper method to check if a character is a vowel.
"""
return ch in {'a', 'e', 'i', 'o', 'u'}
def vowelStrings(self, words, queries):
"""
:type words: List[str]
:type queries: List[List[int]]
:rtype: List[int]
"""
n = len(words)
prefix_sum = [0] * (n + 1) # Step 1: Build prefix sum array of size n+1
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] # Carry forward previous sum
# If the word starts and ends with a vowel, increment the count
if self.is_vowel(words[i][0]) and self.is_vowel(words[i][-1]):
prefix_sum[i + 1] += 1
# Step 2: Process each query using prefix sum difference
result = []
for l, r in queries:
count = prefix_sum[r + 1] - prefix_sum[l]
result.append(count)
# Step 3: Return the result list
return resultJavascript
// Approach: Prefix Sum Optimization
// Language: JavaScript
/**
* @param {string[]} words
* @param {number[][]} queries
* @return {number[]}
*/
var vowelStrings = function(words, queries) {
const isVowel = (ch) => {
return ch === 'a' || ch === 'e' || ch === 'i' || ch === 'o' || ch === 'u';
};
const n = words.length;
const prefixSum = new Array(n + 1).fill(0); // Step 1: Initialize prefix sum array
for (let i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i];
// If the word starts and ends with a vowel, increment the count
if (isVowel(words[i][0]) && isVowel(words[i][words[i].length - 1])) {
prefixSum[i + 1]++;
}
}
// Step 2: Answer each query in constant time using the prefix sum array
const result = [];
for (const [l, r] of queries) {
result.push(prefixSum[r + 1] - prefixSum[l]);
}
// Step 3: Return the final result
return result;
};Time Complexity:O(M + N)
Let M be the size of the words array and N be the number of queries.
- Prefix Sum Calculation:
— We iterate through the words array once to build the prefix sum, which takes O(M) time. - Query Processing:
— Each query is answered in O(1) time using the prefix sum array. So, for N queries, this takes O(N) time. - Final Selection:O(M + N)
Space Complexity: O(M )
Our only auxiliary data structure is the prefixSum array, which has size M, so the total space complexity is O(M).
Learning Tip
Now we have successfully tackled this problem, let’s try these similar problems.
Given a binary string s and two integers minJump and maxJump, you start at index 0. You can jump from index i to any index j such that i + minJump <= j <= i + maxJump and s[j] is '0'. Determine if you can reach the last index of the string.