⚡Flashcard Drill➔
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

  1. Precompute a boolean per word indicating whether it is a vowel string.
  2. Build a prefix-sum array over those booleans so each range query is O(1).
  3. Answer each query as prefix[r + 1] - prefix[l].
  4. 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 == 0 would 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems