Count the Number of Vowel Strings in Range - Solution & Explanation
Problem Statement
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.length
Approach Overview
Problem 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 1: Iterative Range Check
This approach involves iterating over the words in the specified range and checking each word to see if it qualifies as a vowel string. We will determine this by inspecting the first and last characters of each word to ascertain if they are vowels. This straightforward method achieves the desired result by making use of a simple loop and conditional checks.
This C program defines a function isVowel to check if a character is a vowel. The countVowelStrings function iterates over the words from index left to right, checking if each word starts and ends with a vowel. If both conditions are true, it increments a counter. The main function demonstrates by counting vowel strings in the example input.
Complexity
Time Complexity: O(N * L), where N is the number of strings in the range and L is the average length of the strings.
Space Complexity: O(1), as no additional space is used apart from a few variables.
Approach 2: Precomputation with Subrange Check
This approach optimizes the problem by preprocessing the array of words to determine the vowel nature of each word. It stores these results, so the counting process for any given range is made efficient by accessing precomputed data.
This C solution preprocesses the words into a boolean array isVowelString, indicating which words are vowel strings. In the function countVowelStrings, it uses this precomputed information to quickly count vowel strings within the given range. This two-step process allows fast range checks at the expense of initial overhead.
Complexity
Time Complexity: Preprocessing takes O(N * L), Range check takes O(R), giving a total of O(N * L + R).
Space Complexity: O(N) for the boolean array storing whether each word is a vowel string.
Approach 3: Simulation
We just need to traverse the string in the interval [left,.. right], and check if it starts and ends with a vowel. If so, the answer plus one.
After the traversal, return the answer.
The time complexity is O(m), and the space complexity is O(1). Where m = right - left + 1.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Range Check | Time Complexity: O(N * L), where N is the number of strings in the range and L is the average length of the strings. |
| Precomputation with Subrange Check | Time Complexity: Preprocessing takes O(N * L), Range check takes O(R), giving a total of O(N * L + R). |
| Simulation | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Count the Number of Vowel Strings in Range | Leetcode 2586 • Technosage • 5,298 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count the Number of Vowel Strings in Range easy or hard?
Count the Number of Vowel Strings in Range Python/Java solution
How to solve Count the Number of Vowel Strings in Range in O(n)?
What is the best approach for Count the Number of Vowel Strings in Range?
Is Count the Number of Vowel Strings in Range asked at Google/Amazon/Meta?
What data structure is used in Count the Number of Vowel Strings in Range?
What is the time complexity of Count the Number of Vowel Strings in Range?
Ready to solve this problem?
Practice Count the Number of Vowel Strings in Range with our built-in code editor and test cases.
Practice on FleetCode