# Count the Number of Vowel Strings in Range
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-the-number-of-vowel-strings-in-range)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-vowel-strings-in-range
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, String
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal)
---
## Problem
You are given a **0-indexed** array of string `words` and two integers `left` and `right`.

A string is called a **vowel string** if it starts with a vowel character and ends with a vowel character where vowel characters are `'a'`, `'e'`, `'i'`, `'o'`, and `'u'`.

Return _the number of vowel strings_ `words[i]` _where_ `i` _belongs to the inclusive range_ `[left, right]`.

**Example 1:**

**Input:** words = ["are","amy","u"], left = 0, right = 2
**Output:** 2
**Explanation:** 
- "are" is a vowel string because it starts with 'a' and ends with 'e'.
- "amy" is not a vowel string because it does not end with a vowel.
- "u" is a vowel string because it starts with 'u' and ends with 'u'.
The number of vowel strings in the mentioned range is 2.

**Example 2:**

**Input:** words = ["hey","aeo","mu","ooo","artro"], left = 1, right = 4
**Output:** 3
**Explanation:** 
- "aeo" is a vowel string because it starts with 'a' and ends with 'o'.
- "mu" is not a vowel string because it does not start with a vowel.
- "ooo" is a vowel string because it starts with 'o' and ends with 'o'.
- "artro" is a vowel string because it starts with 'a' and ends with 'o'.
The number of vowel strings in the mentioned range is 3.

**Constraints:**

* `1 <= words.length <= 1000`
* `1 <= words[i].length <= 10`
* `words[i]` consists of only lowercase English letters.
* `0 <= left <= right < words.length`

# Approaches
## Prefix Sum Approach
This approach involves pre-calculating the number of vowel strings up to each index. We create a prefix sum array where each element `prefix[i]` stores the count of vowel strings in the original array from the start up to index `i-1`. Once this array is built, the number of vowel strings in any given range `[left, right]` can be found in constant time by subtracting `prefix[left]` from `prefix[right+1]`. While this is powerful for multiple queries, it's less efficient for a single query due to the upfront cost and extra space.
**Time:** O(N), where N is the total number of strings in the `words` array. We must iterate through the entire array once to build the prefix sum array, regardless of the size of the `[left, right]` range. · **Space:** O(N), where N is the total number of strings in the `words` array. This is required to store the prefix sum array.
**Pros:** Extremely fast (`O(1)`) for subsequent queries on the same `words` array after the initial `O(N)` setup.
**Cons:** Higher space complexity (`O(N)`) compared to a simple loop.; For a single query, it performs unnecessary work by processing words outside the `[left, right]` range.; Overall less efficient than a direct iteration for this specific problem statement which only asks for one range query.
### Explanation
The core idea is to trade space for time, particularly for answering multiple range queries. However, for a single query, this trade-off is not beneficial.

1.  First, we create an integer array, let's call it `prefixSum`, of size `words.length + 1`. This array will store the cumulative count of vowel strings.
2.  We iterate through the input `words` array from the beginning. For each word, we check if it's a vowel string.
3.  We populate the `prefixSum` array such that `prefixSum[i+1] = prefixSum[i] + (1 if words[i] is a vowel string, else 0)`.
4.  After this one-time pass, `prefixSum[k]` holds the total count of vowel strings in the sub-array `words[0...k-1]`.
5.  To find the count in the range `[left, right]`, we can use the pre-computed values: `count = prefixSum[right + 1] - prefixSum[left]`. This works because `prefixSum[right + 1]` is the count up to index `right`, and `prefixSum[left]` is the count up to index `left - 1`. Their difference gives the count for the exact range `[left, right]`.

```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 left, int right) {
        int n = words.length;
        int[] prefixSum = new int[n + 1];

        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i];
            String word = words[i];
            if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) {
                prefixSum[i + 1]++;
            }
        }

        return prefixSum[right + 1] - prefixSum[left];
    }
}
```
### Algorithm
- Create a helper method or use a set/string to check for vowels.
- Initialize a `prefixSum` array of size `n + 1`, where `n` is the number of words.
- Iterate from `i = 0` to `n-1` to build the `prefixSum` array.
- For each word `words[i]`, check if it's a vowel string (starts and ends with a vowel).
- The value `prefixSum[i+1]` is calculated as `prefixSum[i]` plus 1 if `words[i]` is a vowel string, otherwise it's the same as `prefixSum[i]`.
- After populating the array, the result for the range `[left, right]` is calculated as `prefixSum[right + 1] - prefixSum[left]`.

## Direct Iteration over the Range
This is the most straightforward and efficient approach for a single query. We iterate through the `words` array only within the specified range `[left, right]`. For each word in this range, we check if it meets the criteria of a vowel string (starts and ends with a vowel). A counter is maintained and incremented for each valid string found.
**Time:** O(R), where R is the size of the range (`right - left + 1`). The loop runs exactly R times. In the worst case, R can be N (the total number of words), making the complexity O(N). · **Space:** O(1). We only use a few variables to store the count and loop index, which does not depend on the input size.
**Pros:** Optimal time complexity for a single query, as it only processes the necessary elements.; Optimal space complexity (`O(1)`).; Simple and easy to understand and implement.
**Cons:** If multiple queries were required on the same `words` array, this approach would be less efficient than a pre-computation method, as it would re-calculate checks for overlapping ranges.
### Explanation
This method directly solves the problem without any pre-computation. It focuses only on the elements within the given `[left, right]` range, making it highly efficient for a single query.

1.  Initialize an integer `count` to zero. This variable will store our final result.
2.  We loop from the `left` index to the `right` index, inclusive. This ensures we only inspect the words relevant to the query.
3.  In each iteration, we retrieve the current word `words[i]`.
4.  We then check if this word is a "vowel string". A helper function `isVowel(char c)` can make the code cleaner. A string is a vowel string if `isVowel(word.charAt(0))` and `isVowel(word.charAt(word.length() - 1))` are both true.
5.  If the condition is met, we increment our `count`.
6.  After the loop completes, `count` holds the total number of vowel strings in the specified range, and we return it.

```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 left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            String word = words[i];
            if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter variable `count` to 0.
- Create a helper function or use a `Set` of vowels (`{'a', 'e', 'i', 'o', 'u'}`) for efficient `O(1)` vowel checks.
- Loop through the `words` array with an index `i` starting from `left` and ending at `right` (inclusive).
- Inside the loop, for each `word = words[i]`:
  - Get the first character, `word.charAt(0)`.
  - Get the last character, `word.charAt(word.length() - 1)`.
  - Check if both the first and last characters are vowels.
  - If both are vowels, increment the `count`.
- After the loop finishes, return the final `count`.

# Solutions
### Java

```java
class Solution {
public
  int vowelStrings(String[] words, int left, int right) {
    int ans = 0;
    for (int i = left; i <= right; ++i) {
      var w = words[i];
      if (check(w.charAt(0)) && check(w.charAt(w.length() - 1))) {
        ++ans;
      }
    }
    return ans;
  }
private
  boolean check(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
  }
}

```

### CPP

```cpp
class Solution {
public:
  int vowelStrings(vector<string> &words, int left, int right) {
    auto check = [](char c) -> bool {
      return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    };
    int ans = 0;
    for (int i = left; i <= right; ++i) {
      auto w = words[i];
      ans += check(w[0]) && check(w[w.size() - 1]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def vowelStrings(self, words: List[str], left: int, right: int) -> int: return sum(
        w[0] in 'aeiou' and w[- 1] in 'aeiou' for w in words[left: right + 1])

```