Count the Number of Vowel Strings in Range solution and explanation
9 more videos on this problem
Count the Number of Vowel Strings in Range | Leetcode 2586Technosage · 8:06 · 5K views
Leetcode | 2586. Count the Number of Vowel Strings in Range | Easy | Java SolutionDeveloper Docs · 8:30 · 767 views
LeetCode#2586 Count the Number of Vowel Strings in Range - PythonCodeJulian · 1:00 · 476 views
Count the Number of Vowel Strings in Range || Implementation || Faang Interview QuestionAryan Mittal · 2:05 · 433 views
2586. Count the Number of Vowel Strings in Range | LeetCode Contest 336 | C++Priyanshi Porwal · 4:46 · 255 views
Leetcode 2586 Count the Number of Vowel Strings in RangeAlgorithmicIQ · 12:14 · 225 views
2586. Count the Number of Vowel Strings in Range (Leetcode Easy)Programming Live with Larry · 2:19 · 224 views
[Leetcode Weekly 336] 2586 - Count the Number of Vowel Strings in RangeSandeep Kumar · 7:10 · 211 views
2586. Count the Number of Vowel Strings in Range - JAVA (Weekly Contest 336)Sourin Majumdar · 2:04 · 167 views
Count the Number of Vowel Strings in Range | Leetcode 2586 | Contest 336Tech Courses · 2:00 · 134 views
The 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 <= 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.
def is_vowel(c):
return c in 'aeiou'
def count_vowel_strings(words, left, right):
count = 0
for i in range(left, right + 1):
if is_vowel(words[i][0]) and is_vowel(words[i][-1]):
count += 1
return count
words = ['are', 'amy', 'u']
result = count_vowel_strings(words, 0, 2)
print(result)public class VowelStringCounter {
public static boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
public static int countVowelStrings(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;
}
public static void main(String[] args) {
String[] words = {"are", "amy", "u"};
int result = countVowelStrings(words, 0, 2);
System.out.println(result);
}
}#include <iostream>
#include <vector>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countVowelStrings(std::vector<std::string>& words, int left, int right) {
int count = 0;
for (int i = left; i <= right; ++i) {
const std::string& word = words[i];
if (isVowel(word.front()) && isVowel(word.back())) {
count++;
}
}
return count;
}
int main() {
std::vector<std::string> words = {"are", "amy", "u"};
int result = countVowelStrings(words, 0, 2);
std::cout << result << std::endl;
return 0;
}function isVowel(c) {
return "aeiou".includes(c);
}
function countVowelStrings(words, left, right) {
let count = 0;
for (let i = left; i <= right; ++i) {
if (isVowel(words[i][0]) && isVowel(words[i][words[i].length - 1])) {
count++;
}
}
return count;
}
const words = ["are", "amy", "u"];
const result = countVowelStrings(words, 0, 2);
console.log(result);#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countVowelStrings(char *words[], int left, int right) {
int count = 0;
for (int i = left; i <= right; ++i) {
int len = strlen(words[i]);
if (isVowel(words[i][0]) && isVowel(words[i][len - 1])) {
count++;
}
}
return count;
}
int main() {
char *words[] = {"are", "amy", "u"};
int result = countVowelStrings(words, 0, 2);
printf("%d", result);
return 0;
}using System;
public class VowelStrings {
public static bool IsVowel(char c) {
return "aeiou".Contains(c);
}
public static int CountVowelStrings(string[] words, int left, int right) {
int count = 0;
for (int i = left; i <= right; ++i) {
if (IsVowel(words[i][0]) && IsVowel(words[i][words[i].Length - 1])) {
count++;
}
}
return count;
}
public static void Main() {
string[] words = {"are", "amy", "u"};
int result = CountVowelStrings(words, 0, 2);
Console.WriteLine(result);
}
}This Python implementation defines a function is_vowel to check for vowels. The function count_vowel_strings evaluates each word in the given range to confirm whether its first and last characters are vowels, counting those that satisfy this condition. An example case evaluates this logic on a predefined list of words.
Time Complexity: O(N * L), where N is the number of words in the specified range and L is their average length.
Space Complexity: O(1), since the only space used is for 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.
def is_vowel(c):
return c in 'aeiou'
def preprocess_vowel_strings(words):
return [is_vowel(word[0]) and is_vowel(word[-1]) for word in words]
def count_vowel_strings(is_vowel_string, left, right):
return sum(is_vowel_string[left:right+1])
words = ['are', 'amy', 'u']
is_vowel_string = preprocess_vowel_strings(words)
result = count_vowel_strings(is_vowel_string, 0, 2)
print(result)import java.util.ArrayList;
import java.util.List;
public class VowelStringCounter {
public static boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public static void preprocessVowelStrings(String[] words, List<Boolean> isVowelString) {
for (String word : words) {
isVowelString.add(isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1)));
}
}
public static int countVowelStrings(List<Boolean> isVowelString, int left, int right) {
int count = 0;
for (int i = left; i <= right; ++i) {
if (isVowelString.get(i)) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String[] words = {"are", "amy", "u"};
List<Boolean> isVowelString = new ArrayList<>();
preprocessVowelStrings(words, isVowelString);
int result = countVowelStrings(isVowelString, 0, 2);
System.out.println(result);
}
}#include <iostream>
#include <vector>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
void preprocessVowelStrings(const std::vector<std::string>& words, std::vector<bool>& isVowelString) {
int size = words.size();
isVowelString.resize(size);
for (int i = 0; i < size; ++i) {
const std::string& word = words[i];
isVowelString[i] = isVowel(word.front()) && isVowel(word.back());
}
}
int countVowelStrings(const std::vector<bool>& isVowelString, int left, int right) {
int count = 0;
for (int i = left; i <= right; ++i) {
if (isVowelString[i]) {
count++;
}
}
return count;
}
int main() {
std::vector<std::string> words = {"are", "amy", "u"};
std::vector<bool> isVowelString;
preprocessVowelStrings(words, isVowelString);
int result = countVowelStrings(isVowelString, 0, 2);
std::cout << result << std::endl;
return 0;
}function isVowel(c) {
return "aeiou".includes(c);
}
function preprocessVowelStrings(words) {
return words.map(word => isVowel(word[0]) && isVowel(word[word.length - 1]));
}
function countVowelStrings(isVowelString, left, right) {
let count = 0;
for (let i = left; i <= right; ++i) {
if (isVowelString[i]) {
count++;
}
}
return count;
}
const words = ["are", "amy", "u"];
const isVowelString = preprocessVowelStrings(words);
const result = countVowelStrings(isVowelString, 0, 2);
console.log(result);#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
void preprocessVowelStrings(char* words[], bool isVowelString[], int size) {
for (int i = 0; i < size; ++i) {
int len = strlen(words[i]);
if (isVowel(words[i][0]) && isVowel(words[i][len - 1])) {
isVowelString[i] = true;
} else {
isVowelString[i] = false;
}
}
}
int countVowelStrings(bool isVowelString[], int left, int right) {
int count = 0;
for (int i = left; i <= right; ++i) {
if (isVowelString[i]) {
count++;
}
}
return count;
}
int main() {
char* words[] = {"are", "amy", "u"};
int size = sizeof(words) / sizeof(words[0]);
bool isVowelString[size];
preprocessVowelStrings(words, isVowelString, size);
int result = countVowelStrings(isVowelString, 0, 2);
printf("%d", result);
return 0;
}using System;
using System.Collections.Generic;
public class VowelStrings {
public static bool IsVowel(char c) {
return "aeiou".Contains(c);
}
public static List<bool> PreprocessVowelStrings(string[] words) {
List<bool> isVowelString = new List<bool>();
foreach (string word in words) {
isVowelString.Add(IsVowel(word[0]) && IsVowel(word[word.Length - 1]));
}
return isVowelString;
}
public static int CountVowelStrings(List<bool> isVowelString, int left, int right) {
int count = 0;
for (int i = left; i <= right; ++i) {
if (isVowelString[i]) {
count++;
}
}
return count;
}
public static void Main() {
string[] words = {"are", "amy", "u"};
List<bool> isVowelString = PreprocessVowelStrings(words);
int result = CountVowelStrings(isVowelString, 0, 2);
Console.WriteLine(result);
}
}This Python solution preprocesses the words into a list of booleans, where each boolean represents whether the corresponding word is a vowel string. The precomputed data allows for a quick summation to count vowel strings within a range, enhancing performance for multiple queries on the same dataset.
Time Complexity: Preprocessing O(N * L), Counting range O(R), for a total of O(N * L + R).
Space Complexity: O(N), due to storing boolean indicators for each word.
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.
function vowelStrings(words: string[], left: number, right: number): number {
let ans = 0;
const check: string[] = ['a', 'e', 'i', 'o', 'u'];
for (let i = left; i <= right; ++i) {
const w = words[i];
if (check.includes(w[0]) && check.includes(w.at(-1))) {
++ans;
}
}
return ans;
}func vowelStrings(words []string, left int, right int) (ans int) {
check := func(c byte) bool {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
}
for _, w := range words[left : right+1] {
if check(w[0]) && check(w[len(w)-1]) {
ans++
}
}
return
}impl Solution {
pub fn vowel_strings(words: Vec<String>, left: i32, right: i32) -> i32 {
let check =
|c: u8| -> bool { c == b'a' || c == b'e' || c == b'i' || c == b'o' || c == b'u' };
let mut ans = 0;
for i in left..=right {
let w = words[i as usize].as_bytes();
if check(w[0]) && check(w[w.len() - 1]) {
ans += 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Range Check | Time Complexity: O(N * L), where N is the number of words in the specified range and L is their average length. |
| Precomputation with Subrange Check | Time Complexity: Preprocessing O(N * L), Counting range O(R), for a total of O(N * L + R). |
| Simulation | – |
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 |
Frequently asked questions
Is Count the Number of Vowel Strings in Range easy or hard?
The problem is classified as Easy on LeetCode. It focuses on basic array iteration and string character checks, making it suitable for beginners practicing counting and conditional logic.
Count the Number of Vowel Strings in Range Python/Java solution
In Python or Java, iterate from left to right and check if word[0] and word[word.length-1] are vowels. Maintain a counter for valid words. The algorithm runs in O(n) time and uses O(1) additional memory.
How to solve Count the Number of Vowel Strings in Range in O(n)?
Traverse the array within the given index range and check two characters for each word: the first and the last. If both belong to the vowel set (a, e, i, o, u), increment the count. Since each word requires constant work, the total complexity is O(n).
What is the best approach for Count the Number of Vowel Strings in Range?
The most practical approach is a simple iterative range check. Iterate from index left to right and verify whether each word starts and ends with a vowel. This runs in O(n) time and O(1) space, which is optimal for a single query.
Is Count the Number of Vowel Strings in Range asked at Google/Amazon/Meta?
Problems like this appear frequently in screening rounds because they test basic string processing and array traversal. Variants involving prefix sums or range queries are common in interviews at companies such as Amazon, Google, and Meta.
What data structure is used in Count the Number of Vowel Strings in Range?
The core solution uses a simple array traversal with constant-time string access. Some implementations also use a small hash set or lookup table to check whether a character is a vowel.
What is the time complexity of Count the Number of Vowel Strings in Range?
The standard solution runs in O(n) time where n is the number of words inspected between left and right. Each word only requires constant-time checks on its first and last characters. Space complexity is O(1).