Watch 10 video solutions for Count the Number of Vowel Strings in Range, a easy level problem involving Array, String, Counting. This walkthrough by Technosage has 4,869 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 10001 <= words[i].length <= 10words[i] consists of only lowercase English letters.0 <= left <= right < words.lengthProblem Overview: You receive an array of words and two indices left and right. The task is to count how many words within that inclusive range both start and end with a vowel (a, e, i, o, u). The check is purely string-based and limited to the given subarray.
Approach 1: Iterative Range Check (O(n) time, O(1) space)
Iterate through the array only between indices left and right. For each word, check whether the first and last characters belong to the vowel set. A simple membership check like set.contains(char) or a direct comparison against five vowels is enough. Increment a counter whenever both conditions are satisfied. This approach relies on straightforward iteration over the array and constant-time string character access.
The key insight: only the boundary characters matter. You never need to scan the entire word. This keeps the operation constant time per element. Time complexity is O(n) for the scanned portion of the array and space complexity is O(1).
Approach 2: Precomputation with Subrange Check (Prefix Count) (O(n) preprocessing, O(1) query, O(n) space)
If multiple range queries are expected, precompute a prefix array where prefix[i] stores how many valid vowel strings appear from index 0 to i. While building this array, perform the same first-and-last vowel check and accumulate counts. After preprocessing, the number of valid strings in any range [left, right] becomes prefix[right] - prefix[left-1].
This technique converts repeated scanning into constant-time queries. It uses a classic prefix-sum pattern frequently seen in counting and range query problems. Preprocessing takes O(n) time and O(n) space, while each query runs in O(1).
Recommended for interviews: The iterative range check is the expected solution. It is simple, readable, and runs in linear time with constant space. Mentioning the prefix-count optimization shows stronger problem-solving depth, especially when discussing how to scale the solution for multiple range queries.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Range Check | O(n) | O(1) | Best for a single query over the given range |
| Prefix Precomputation (Subrange Check) | O(n) preprocessing, O(1) query | O(n) | Useful when multiple range queries must be answered quickly |