Count the Number of Vowel Strings in Range

EASY

Description

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

Checkout 2 different approaches to solve Count the Number of Vowel Strings in Range. Click on different approaches to view the approach and algorithm in detail.

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.

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

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.

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.
We iterate through the input words array from the beginning. For each word, we check if it's a vowel string.
We populate the prefixSum array such that prefixSum[i+1] = prefixSum[i] + (1 if words[i] is a vowel string, else 0).
After this one-time pass, prefixSum[k] holds the total count of vowel strings in the sub-array words[0...k-1].
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 Analysis

Time Complexity: 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 Complexity: O(N), where N is the total number of strings in the `words` array. This is required to store the prefix sum array.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count the Number of Vowel Strings in Range. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Count the Number of Vowel Strings in Range

Patterns:

Counting

Data Structures:

ArrayString

Companies:

PayPal |