Count Vowel Strings in Ranges — Editorial

Opening the reading…

Intuitionwhy each range becomes a subtraction

Each word contributes only one bit of information to every query: it either starts and ends with vowels, or it does not. First classify words[i] as 1 when both boundary characters are vowels and as 0 otherwise. The interior characters do not affect the answer, so examining them would add work without adding information.

Once the array contains only zeros and ones, store cumulative totals in a prefix array. Let prefix[i] count qualifying words before index i. Then the inclusive range l to r is exactly the total before r + 1 minus the total before l. The extra slot at prefix[0] makes this formula work unchanged when l is zero.

Approachclassify once, subtract for every query

Create a prefix array of length n + 1 filled with zero, because prefix[i] will represent the first i words and prefix[0] must describe an empty prefix.

For each word at index i, test its first and last characters against the vowel set, because a word qualifies only when both endpoints are vowels.

Set prefix[i + 1] to prefix[i] plus one for a qualifying word or zero otherwise, because every prefix must include all earlier classifications exactly once.

For each query [l, r], read the inclusive endpoints and compute prefix[r + 1] - prefix[l], because prefix[r + 1] includes the entire requested range while prefix[l] removes everything before it.

Append the computed value to the answer array in query order, because the result at position i must correspond to the i-th query and the output array is allowed to grow independently of the prefix array.

Complexitythe preprocessing cost is paid once

MEASURE	BOUND	WHY
Time	O(n + q)	Each word contributes one prefix entry after two constant-time endpoint checks, and each query performs two array lookups and one subtraction. No word or query is revisited, so the two passes add rather than multiply their work.
Space	O(n) extra	The prefix array stores n + 1 cumulative values. The returned answer array is required output and is excluded from the extra-space bound. There is no input-shape degradation: the extra working space remains O(n) whether all words qualify, none qualify, or the qualifying words are clustered.

Here n is the number of words and q is the number of queries. The word length is bounded, so checking two endpoints takes constant time per word.

Annotated solutionC++ · prefix array with an empty-prefix slot

CPPBuild the prefix counts once, then answer each inclusive query by subtraction.

#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        int n = static_cast<int>(words.size());
        vector<int> prefix(n + 1, 0);
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};

        for (int i = 0; i < n; ++i) {
            string& word = words[i];
            bool qualifies = vowels.count(word[0]) && vowels.count(word.back());
            prefix[i + 1] = prefix[i] + (qualifies ? 1 : 0);
        }

        vector<int> answer;
        answer.reserve(queries.size());
        for (const vector<int>& query : queries) {
            int left = query[0];
            int right = query[1];
            answer.push_back(prefix[right + 1] - prefix[left]);
        }

        return answer;
    }
};

The indexing convention carries the main insight. prefix[i] stops before words[i], so prefix[left] removes exactly the elements before the query. The right endpoint is inclusive, which is why the kept total ends at prefix[right + 1]. The classification uses word[0] and word.back() only; checking the complete word would solve a different problem.