Prefix Sum/Count Vowel Strings in RangesMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Count Vowel Strings in Ranges

Prefix Sum·Medium

You are given a 0-indexed array of strings words and a 2D array of integers queries.

Each query queries[i] = [l, r] asks for the number of strings words[j] such that l <= j <= r and words[j] starts and ends with a vowel (a, e, i, o, or u).

Return an array ans of size queries.length where ans[i] is the answer to the i-th query.

The classic prefix-sum approach: build a cumulative count of vowel-bounded words once, then answer each [l, r] query in O(1) as prefix[r + 1] - prefix[l].

Examples

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]

Output: [2,3,0]

The vowel-bounded words are "aba", "ece", "aa", "e" at indices 0, 2, 3, 4. Query [0,2] covers indices 0,1,2 → 2. Query [1,4] covers 1,2,3,4 → 3. Query [1,1] covers only index 1 ("bcb") → 0.

Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]

Output: [3,2,1]

Constraints

1 <= words.length <= 10^5
1 <= words[i].length <= 40
words[i] consists of lowercase English letters only.
sum of words[i].length <= 3 * 10^5
1 <= queries.length <= 10^5
0 <= queries[j][0] <= queries[j][1] < words.length

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Prefix Sum
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.