2559. Count Vowel Strings in Ranges
Asked at Atlassian
Difficulty
Medium
Time
O(n + q)
Space
O(n)
Pattern
Array
Companies
1
Problem
You get an array of lowercase words called words, and a list of queries. Each query is a pair [left, right] and asks one question: how many words in words[left..right] (both ends included) start with a vowel and also end with a vowel?
The vowels are a, e, i, o, u. A word qualifies only if its first letter is a vowel and its last letter is a vowel. A one-letter word like "e" counts, because its first and last letter are the same vowel.
Return an array ans with one number per query, in the same order as the queries. The ranges can overlap, and the same word may be counted in many queries.
Which words qualify, and what each query asks
Constraints
- ●
1 <= words.length <= 10^5 - ●
1 <= words[i].length <= 40 - ●
words[i] consists only of lowercase English letters - ●
sum(words[i].length) <= 3 * 10^5 - ●
1 <= queries.length <= 10^5 - ●
0 <= li <= ri < words.length
Examples
words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]][2,3,0]words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]][3,2,1]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Brute force: for each query, iterate from left to right and check if each word starts and ends with a vowel. That's O(q * n) where q is the number of queries and n is the array length. Works but too slow for large inputs.
Key insight: precompute a prefix sum array where prefix[i] counts the number of vowel-strings from index 0 to i-1. Then each query is answered in O(1) by computing prefix[right+1] - prefix[left].
Why prefix sum works: prefix sums turn range sum queries into two array lookups. If you know the cumulative count up to each index, the count in any range [left, right] is prefix[right+1] - prefix[left]. This is the standard technique for offline range queries.
The check for vowel-string: a word starts and ends with a vowel if word[0] in {a, e, i, o, u} AND word[-1] in {a, e, i, o, u}. A 1-indexed prefix array simplifies the query formula.
Edge cases: single character word that is a vowel (counts), empty words array, queries where left equals right, words with uppercase vowels (assume lowercase only based on constraints).
Optimal Approach
Step 1: Create a boolean array where is_vowel[i] = 1 if words[i] starts and ends with a vowel, else 0.
Step 2: Build a prefix sum array: prefix[0] = 0, prefix[i+1] = prefix[i] + is_vowel[i].
Step 3: For each query [left, right], return prefix[right+1] - prefix[left].
The vowel check: a word w qualifies if w[0] is in {a,e,i,o,u} AND w[-1] is in {a,e,i,o,u}. Single-character vowel words count (start == end).
Walkthrough with words = ["aba","bcb","ece","aa","e"]:
is_vowel = [1, 0, 1, 1, 1]
prefix = [0, 1, 1, 2, 3, 4]
Query [0,2]: prefix[3] - prefix[0] = 2. Words "aba" and "ece" qualify.
Query [1,4]: prefix[5] - prefix[1] = 3. Words "ece", "aa", "e" qualify.
Time: O(n + q) for building prefix and answering all queries. Space: O(n) for the prefix array.
Prefix sums turn each query into a subtraction
What Trips People Up in Real Interviews
Checking only the first character or only the last character. A word must BOTH start AND end with a vowel to count. Check both conditions.
Building a prefix array but using the wrong formula. The correct formula for range [left, right] is prefix[right+1] - prefix[left], not prefix[right] - prefix[left].
Not recognizing this as a prefix sum problem and using brute force for each query. When the interviewer mentions repeated range queries, prefix sums are the first optimization to consider.
Forgetting that single-character vowel words (like "a" or "e") start and end with the same character, which is a vowel. They should be counted.
Using a list instead of a set for vowel lookup. A set gives O(1) membership checks. A list requires O(k) where k is the number of vowels. Use set("aeiou").
Solution Code
O(n + q) timedef vowelStrings(words, queries):
vowels = set('aeiou')
is_v = [1 if w[0] in vowels and w[-1] in vowels else 0 for w in words]
prefix = [0] * (len(is_v) + 1)
for i in range(len(is_v)):
prefix[i + 1] = prefix[i] + is_v[i]
return [prefix[r + 1] - prefix[l] for l, r in queries]Frequently Asked Questions
What is the Count Vowel Strings in Ranges problem?
Given an array of strings words and a 2D array of queries where each query is [left, right], count how many words in the range [left, right] start and end with a vowel. This problem tests prefix sum optimization for repeated range queries.
How do you solve Count Vowel Strings in Ranges?
The optimal approach runs in O(n + q) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Count Vowel Strings in Ranges?
Count Vowel Strings in Ranges is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Count Vowel Strings in Ranges?
- Checking only the first character or only the last character. A word must BOTH start AND end with a vowel to count. Check both conditions.
- Building a prefix array but using the wrong formula. The correct formula for range [left, right] is `prefix[right+1] - prefix[left]`, not `prefix[right] - prefix[left]`.
- Not recognizing this as a prefix sum problem and using brute force for each query. When the interviewer mentions repeated range queries, prefix sums are the first optimization to consider.
- Forgetting that single-character vowel words (like "a" or "e") start and end with the same character, which is a vowel. They should be counted.
- Using a list instead of a set for vowel lookup. A set gives `O(1)` membership checks. A list requires `O(k)` where k is the number of vowels. Use `set("aeiou")`.