Count Vowel Strings in Ranges
Asked at Atlassian
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.
Asked At
| 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).
Visual walkthrough for words = ["aba","bcb","ece","aa","e"]:
is_vowel_string: [True, False, True, True, True] = [1, 0, 1, 1, 1]
prefix = [0, 1, 1, 2, 3, 4]
Query [0,2]: prefix[3] - prefix[0] = 2 - 0 = 2 ("aba" and "ece")
Query [1,4]: prefix[5] - prefix[1] = 4 - 1 = 3 ("ece", "aa", "e")
Query [2,2]: prefix[3] - prefix[2] = 2 - 1 = 1 ("ece")
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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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")`.