# Count Vowel Strings in Ranges
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-vowel-strings-in-ranges)
Canonical: https://scaleengineer.com/dsa/problems/count-vowel-strings-in-ranges
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, String
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [IBM](https://scaleengineer.com/companies/ibm), [PayPal](https://scaleengineer.com/companies/paypal)
---
## Problem
You are given a **0-indexed** array of strings `words` and a 2D array of integers `queries`.

Each query `queries[i] = [li, ri]` asks us to find the number of strings present at the indices ranging from `li` to `ri` (both **inclusive**) of `words` that start and end with a vowel.

Return _an array_ `ans` _of size_ `queries.length`_, where_ `ans[i]` _is the answer to the_ `i`th _query_.

**Note** that the vowel letters are `'a'`, `'e'`, `'i'`, `'o'`, and `'u'`.

**Example 1:**

**Input:** words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
**Output:** [2,3,0]
**Explanation:** The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
The answer to the query [0,2] is 2 (strings "aba" and "ece").
to query [1,4] is 3 (strings "ece", "aa", "e").
to query [1,1] is 0.
We return [2,3,0].

**Example 2:**

**Input:** words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
**Output:** [3,2,1]
**Explanation:** Every string satisfies the conditions, so we return [3,2,1].

**Constraints:**

* `1 <= words.length <= 105`
* `1 <= words[i].length <= 40`
* `words[i]` consists only of lowercase English letters.
* `sum(words[i].length) <= 3 * 105`
* `1 <= queries.length <= 105`
* `0 <= li <= ri < words.length`

# Approaches
## Brute Force Iteration for Each Query
The most straightforward approach is to handle each query independently. For every query `[l, r]`, we can iterate through the `words` array from index `l` to `r`. In each iteration, we check if the current word starts and ends with a vowel. We maintain a counter for the current query, incrementing it whenever we find such a word. After checking all words in the range, the value of the counter is the answer for that query.
**Time:** O(Q * N), where Q is the number of queries and N is the number of words. For each of the Q queries, we might iterate through up to N words in the worst case (e.g., a query `[0, N-1]`). This leads to a quadratic time complexity which is too slow for the given constraints. · **Space:** O(Q) to store the answer array. If the output array is not considered as extra space, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Requires minimal extra space (besides the output array).
**Cons:** Highly inefficient due to redundant computations for overlapping query ranges.; Fails to pass time limits on platforms like LeetCode for the given constraints.
### Explanation
This method directly translates the problem statement into code. It processes one query at a time. For a query `[l, r]`, it sets up a loop from `l` to `r` and, for each word, performs a check. This check involves accessing the first and last characters of the string and verifying if they are vowels. While simple, this approach re-evaluates the same words if they appear in multiple query ranges, leading to significant performance issues with a large number of words and queries.

```java
class Solution {
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    public int[] vowelStrings(String[] words, int[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int count = 0;
            for (int j = l; j <= r; j++) {
                String word = words[j];
                if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) {
                    count++;
                }
            }
            ans[i] = count;
        }
        return ans;
    }
}
```
### Algorithm
1. Initialize an integer array `ans` of size `queries.length` to store the results.
2. Create a helper function `isVowel(char c)` which returns `true` if `c` is one of 'a', 'e', 'i', 'o', 'u', and `false` otherwise.
3. Iterate through each query `queries[i] = [l, r]`.
4. For each query, initialize a counter `count = 0`.
5. Start a nested loop that iterates through the `words` array from index `l` to `r` (inclusive).
6. For each `word` in this range, get its first character `firstChar` and last character `lastChar`.
7. Use the `isVowel` helper function to check if both `firstChar` and `lastChar` are vowels.
8. If the condition is met, increment the `count`.
9. After the inner loop completes, assign the final `count` to `ans[i]`.
10. After iterating through all queries, return the `ans` array.

## Prefix Sum Precomputation
A much more efficient approach is to precompute the counts to answer range queries quickly. The problem of finding the number of items with a certain property in a range is a classic application of the prefix sum technique. We can first determine for each word if it's a "vowel string" (starts and ends with a vowel). Then, we can build a prefix sum array on top of this information. The prefix sum array, `prefixCounts`, will store at index `i` the cumulative count of vowel strings from the beginning of the `words` array up to index `i-1`. With this `prefixCounts` array, the answer to any query `[l, r]` can be found in constant time by calculating `prefixCounts[r+1] - prefixCounts[l]`.
**Time:** O(N + Q), where N is the number of words and Q is the number of queries. We perform one pass over the `words` array to build the prefix sum array (O(N)), and one pass over the `queries` array to compute the answers (O(Q)). Each query is answered in O(1) time. This is very efficient and well within the time limits. · **Space:** O(N), where N is the length of `words`. This is the auxiliary space required to store the prefix sum array.
**Pros:** Highly efficient, with linear time complexity.; Answers each range query in constant time after the initial precomputation.
**Cons:** Requires extra space proportional to the number of words to store the prefix sum array.
### Explanation
This approach involves two main phases: precomputation and query processing. 

In the precomputation phase, we iterate through the `words` array just once. We maintain a running count of vowel strings and store it in a `prefixCounts` array. `prefixCounts[i+1]` will store the total number of vowel strings found in the subarray `words[0...i]`. 

In the query processing phase, we can answer any range query `[l, r]` instantly. The count of vowel strings from index `l` to `r` is simply the total count up to `r` minus the total count up to `l-1`. Using our `prefixCounts` array, this translates to `prefixCounts[r+1] - prefixCounts[l]`. This decouples the query processing time from the size of the range, making it extremely fast.

```java
class Solution {
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    public int[] vowelStrings(String[] words, int[][] queries) {
        int n = words.length;
        int[] prefixCounts = new int[n + 1];
        
        // Build the prefix sum array
        for (int i = 0; i < n; i++) {
            String word = words[i];
            int vowelFlag = 0;
            if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) {
                vowelFlag = 1;
            }
            prefixCounts[i + 1] = prefixCounts[i] + vowelFlag;
        }
        
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            // The count for range [l, r] is count(0..r) - count(0..l-1)
            // which corresponds to prefixCounts[r+1] - prefixCounts[l]
            ans[i] = prefixCounts[r + 1] - prefixCounts[l];
        }
        
        return ans;
    }
}
```
### Algorithm
1. Create a prefix sum array, `prefixCounts`, of size `N + 1`, where `N` is the length of the `words` array. Initialize `prefixCounts[0] = 0`.
2. Create a helper function `isVowel(char c)`.
3. Iterate through the `words` array from `i = 0` to `N-1`.
4. For each `word`, check if it starts and ends with a vowel.
5. Calculate the value for the current position in the prefix sum array: `prefixCounts[i+1] = prefixCounts[i] + (1 if the word is a vowel string, else 0)`.
6. After this single pass, the `prefixCounts` array is fully populated. `prefixCounts[k]` now holds the count of vowel strings in `words[0...k-1]`.
7. Initialize an answer array `ans` of size `Q`, where `Q` is the number of queries.
8. Iterate through each query `[l, r]`.
9. The number of vowel strings in the range `[l, r]` is the total count up to index `r` minus the total count up to index `l-1`. This can be calculated in O(1) time as `prefixCounts[r + 1] - prefixCounts[l]`.
10. Store this result in the `ans` array.
11. Return `ans`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer> nums = new ArrayList<>();
public
  int[] vowelStrings(String[] words, int[][] queries) {
    Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
    for (int i = 0; i < words.length; ++i) {
      char a = words[i].charAt(0), b = words[i].charAt(words[i].length() - 1);
      if (vowels.contains(a) && vowels.contains(b)) {
        nums.add(i);
      }
    }
    int m = queries.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      int l = queries[i][0], r = queries[i][1];
      ans[i] = search(r + 1) - search(l);
    }
    return ans;
  }
private
  int search(int x) {
    int l = 0, r = nums.size();
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums.get(mid) >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> vowelStrings(vector<string> &words,
                           vector<vector<int>> &queries) {
    unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
    vector<int> nums;
    for (int i = 0; i < words.size(); ++i) {
      char a = words[i][0], b = words[i].back();
      if (vowels.count(a) && vowels.count(b)) {
        nums.push_back(i);
      }
    }
    vector<int> ans;
    for (auto &q : queries) {
      int l = q[0], r = q[1];
      int cnt = upper_bound(nums.begin(), nums.end(), r) -
                lower_bound(nums.begin(), nums.end(), l);
      ans.push_back(cnt);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]: vowels = set("aeiou") nums = [i for i, w in enumerate(words) if w[0] in vowels and w[- 1] in vowels] return [bisect_right(nums, r) - bisect_left(nums, l) for l, r in queries]

```