Scale Engineer

Count the Number of Vowel Strings in Range

Easy
#2366Time: 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.1 company
Patterns
Counting
Data structures
ArrayString
Companies
PayPal

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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].

Walkthrough

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].
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];    }}

Complexity

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.

Trade-offs

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.

Solutions

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';  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem