Count Vowel Strings in Ranges

medium prefix sum range query string

Problem

You are given a 0-indexed array of strings words and a list of queries. Each query [l, r] asks how many strings at indices l through r (inclusive) both start and end with a vowel (a, e, i, o, u). Return an array with the answer to every query.

Inputwords = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]

Output[2,3,0]

Vowel-bounded words are "aba", "ece", "aa", "e". Query [0,2] → 2, [1,4] → 3, [1,1] → 0.

words (comma-separated)

queries (l:r, comma-separated)

def vowel_strings(words, queries):
    vowels = set("aeiou")
    n = len(words)
    prefix = [0] * (n + 1)
    for i, w in enumerate(words):
        ok = w[0] in vowels and w[-1] in vowels
        prefix[i + 1] = prefix[i] + (1 if ok else 0)
    ans = []
    for l, r in queries:
        ans.append(prefix[r + 1] - prefix[l])
    return ans

function vowelStrings(words, queries) {
  const vowels = new Set(["a", "e", "i", "o", "u"]);
  const n = words.length;
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    const w = words[i];
    const ok = vowels.has(w[0]) && vowels.has(w[w.length - 1]);
    prefix[i + 1] = prefix[i] + (ok ? 1 : 0);
  }
  return queries.map(function (q) {
    return prefix[q[1] + 1] - prefix[q[0]];
  });
}

int[] vowelStrings(String[] words, int[][] queries) {
    String vowels = "aeiou";
    int n = words.length;
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) {
        String w = words[i];
        boolean ok = vowels.indexOf(w.charAt(0)) >= 0
                  && vowels.indexOf(w.charAt(w.length() - 1)) >= 0;
        prefix[i + 1] = prefix[i] + (ok ? 1 : 0);
    }
    int[] ans = new int[queries.length];
    for (int i = 0; i < queries.length; i++)
        ans[i] = prefix[queries[i][1] + 1] - prefix[queries[i][0]];
    return ans;
}

vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
    string vowels = "aeiou";
    int n = words.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        string& w = words[i];
        bool ok = vowels.find(w.front()) != string::npos
               && vowels.find(w.back()) != string::npos;
        prefix[i + 1] = prefix[i] + (ok ? 1 : 0);
    }
    vector<int> ans;
    for (auto& q : queries)
        ans.push_back(prefix[q[1] + 1] - prefix[q[0]]);
    return ans;
}

Explanation

Each word is either valid (its first and last letter are both vowels) or not — a simple yes/no. So we can convert words into a 0/1 array and the question "how many valid words in [l, r]?" becomes "what is the sum of that 0/1 array over [l, r]?".

Summing a sub-range repeatedly is exactly what a prefix sum accelerates. We build prefix of length n + 1 where prefix[i] is the count of valid words among the first i words. The shift by one lets prefix[0] = 0 stand for "nothing counted yet", which removes any edge case when l = 0.

The recurrence is prefix[i + 1] = prefix[i] + isValid(words[i]). After one left-to-right pass, every range sum is available.

A query [l, r] then answers in O(1): prefix[r + 1] - prefix[l]. The larger prefix counts valid words in [0, r]; subtracting the smaller removes [0, l - 1], leaving exactly [l, r].

Building the prefix array is O(n) and each of the q queries is O(1), so the whole solution runs in O(n + q) time — far better than re-scanning the range for every query.

Time: O(n + q) Space: O(n)