2559: Count-Vowel-Strings-in-Ranges
Medium

table of contents

Immediately, when I finished reading the question, I thought of prefix sums.

In my algorithm, I iterated through the words in words and initalised a prefix sum array, pSum. Using pSum, I am then able to return ans in O(n) time, with each ans[i] being calculated in O(1).

(if an array looked like: [a, b, c, d],
then its prefix sum would look like: [a, a+b, a+b+c, a+b+c+d],
meaning if we wanted to find the sum of all elements between e.g. index 1 and 2 inclusive,
we can simply do the operation pSum[2]-pSum[0] to achieve the same result without iterating through the array)

code

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        vector<int> pSum (words.size(), 0);
        unordered_set <char> vowels = {'a', 'e', 'i', 'o', 'u'};
        int counter = 0;
        for (int i = 0; i < pSum.size(); ++i) {
            if (vowels.count(words[i][0]) && vowels.count(words[i][words[i].size()-1]))
                ++counter;
            pSum[i] = counter;
        }

        vector<int> ans (queries.size());
        int temp;
        for (int i = 0; i < queries.size(); ++i) {
            temp = pSum[queries[i][1]];
            if (queries[i][0] > 0) {
                temp -= pSum[queries[i][0]-1];
            }
            ans[i] = temp;
        }

        return ans;
    }
};

complexity