Faangprep Logo
Log inStart free
Browse curriculum

Count Vowels in Ranges

Answer range queries counting the words that start and end with a vowel — one pass to build a prefix count, then one subtraction per query.

MediumSolve on LeetCode

Problem Understanding

You are given a string array words and a 2D array queries. Each query [l, r] asks for the number of strings in words[l...r] that start and end with a vowel.

We need to answer many queries efficiently.

Strategy

  1. Preprocessing: Create a boolean/integer array is_valid where is_valid[i] = 1 if words[i] starts and ends with a vowel, else 0.
  2. Prefix Sum: Compute prefix sum P of is_valid. P[i] = count of valid words in words[0...i-1].
  3. Query: Answer for [l, r] is P[r+1] - P[l].

  • Vowels: a, e, i, o, u

Interactive Visualization

See how we can answer multiple range queries in O(1) time after O(N) preprocessing.

Edge Cases

Consider:

  • Empty Queries: Return empty array.

  • Single Word: Range [0, 0].

  • No Vowels: Prefix sum remains 0.

Dry Run

Words: ['aba', 'bcb', 'ece', 'aa', 'e']. Valid: [1, 0, 1, 1, 1].
Prefix P: [0, 1, 1, 2, 3, 4] (size N+1)

Query Formula P[R+1] - P[L] Values Result
[0, 2] P[3] - P[0] 2 - 0 2 (aba, ece)
[1, 4] P[5] - P[1] 4 - 1 3 (ece, aa, e)

Solution

O(N + Q) Time.

Count Vowels in Ranges Code
1var vowelStrings = function(words, queries) {
2    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
3    const n = words.length;
4    const prefix = new Array(n + 1).fill(0);
5    
6    for (let i = 0; i < n; i++) {
7        const w = words[i];
8        const valid = vowels.has(w[0]) && vowels.has(w[w.length - 1]);
9        prefix[i+1] = prefix[i] + (valid ? 1 : 0);
10    }
11    
12    const ans = [];
13    for (const [l, r] of queries) {
14        ans.push(prefix[r+1] - prefix[l]);
15    }
16    return ans;
17};
Previous

Introduction to Prefix Sums

Next

Product of Array Except Self

The approach, step by step

  1. Allocate the prefix array

    Create prefix with N + 1 zeros.

  2. Test and accumulate each word

    Add 1 to the running count when a word starts and ends with a vowel, and store it in prefix[i + 1].

  3. Answer the queries

    For each [l, r], return prefix[r + 1] - prefix[l].

Frequently asked questions

How do you count vowel strings in a range quickly?

Turn each word into 1 if it starts and ends with a vowel and 0 otherwise, build a prefix sum of those values, and answer a query [l, r] as prefix[r + 1] - prefix[l].

What is the time complexity of Count Vowel Strings in Ranges?

O(N + Q): one pass over the N words to build the prefix array and O(1) for each of the Q queries. Space is O(N) for the prefix array plus O(Q) for the answers.

Does a one-letter word like "e" count?

Yes. Its first and last character are the same letter, so a single vowel both starts and ends the word and it adds 1 to the prefix count.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description