Intuition

We can use “Prefix sum” to solve this problem.

Approach

Define an array prefix_sum, where prefix_sum[i] is the number of vowel strings before words[i], i.e., that present in the range $[0, i-1]$. Naturally, prefix_sum[0] = 0. This prefix_sum can be obtained by iterating through the words from left to right.

The answer for queries[i] = [li, ri], then can be computed by prefix_sum[ri + 1] - prefix_sum[li].

Code

• Python3
• C++

• class Solution:
      def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
          vowels = set("aeiou")
          prefix_sum = [0]
          cnt = 0
          for w in words:
              if w[0] in vowels and w[-1] in vowels:
                  cnt += 1
              prefix_sum.append(cnt)
          res = []
          for l, r in queries:
              res.append(prefix_sum[r + 1] - prefix_sum[l])
          return res
  

• class Solution {
  public:
      vector<int> vowelStrings(vector<string>& words,
                               vector<vector<int>>& queries) {
          vector<int> prefix_sum = {0}, res;
          unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
          int cnt = 0;
          for (auto& w : words) {
              if (vowels.count(w[0]) && vowels.count(w[w.size() - 1])) {
                  cnt += 1;
              }
              prefix_sum.push_back(cnt);
          }
          for (auto& q : queries) {
              res.push_back(prefix_sum[q[1] + 1] - prefix_sum[q[0]]);
          }
          return res;
      }
  };
  

Complexity

Let $N$ be the length of words and $M$ be the length of queries.

• Time complexity: $O(N+M)$
• Space complexity: $O(N)$