NeetCode #90LC-2559MediumArrays & Hashing
← Back to All Problems#90 · #2559 · Count Vowel Strings in Ranges(统计范围内的元音字符串数)
📌 Problem Statement & Constraints
You are given an array of strings
words and an array of queries, each queries[i] = [l, r]. A string is a vowel string if it starts and ends with a vowel. For each query, return the number of vowel strings in words[l..r] inclusive. Constraints: 1 <= words.length <= 10^5, 1 <= queries.length <= 10^5.💡 Core Algorithmic Approaches
- Precompute a boolean per word indicating whether it is a vowel string.
- Build a prefix-sum array over those booleans so each range query is O(1).
- Answer each query as
prefix[r + 1] - prefix[l]. - This is the standard offline range-count pattern: O(n) preprocessing, O(1) per query.
💻 Benchmark Python3 Implementation
class Solution:
def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
vowels = set("aeiou")
n = len(words)
pref = [0] * (n + 1)
for i, w in enumerate(words):
ok = 1 if (w[0] in vowels and w[-1] in vowels) else 0
pref[i + 1] = pref[i] + ok
return [pref[r + 1] - pref[l] for l, r in queries]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + q): O(n) to build the prefix array and O(1) per query.
💾 Space Complexity
O(n) for the prefix array.
⚠️ Interview Pitfalls & Follow-ups
- Recomputing the condition per query: O(n * q) and far too slow for the stated limits.
- Using
words[i][0] in 'aeiou': works, but a set lookup is clearer and avoids the substring-membership gotcha with multi-character strings. - Forgetting the leading zero in the prefix array: then
l == 0would need a special case. - Checking the length-1 word: a single-character word both starts and ends with that character, so the condition correctly evaluates to whether it is a vowel.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.