2586. Count the Number of Vowel Strings in Range
Problem Description
In this problem, you're given an array of strings named words
, and two integers left
and right
that represent the indices within the array. The task is to count how many strings from the sub-array starting at index left
and ending at index right
(both inclusive) are "vowel strings." A vowel string is defined as a string that both starts and ends with a vowel character. The vowels in this case are the characters 'a', 'e', 'i', 'o', and 'u'. The answer you need to provide is the total number of such vowel strings that exist within the specified range of indices in the words
array.
Intuition
The solution approach is fairly straightforward and relies on a direct check of each string within the specified bounds (left
to right
inclusive). For each string, you need to perform two checks: (1) whether the first character is a vowel, and (2) whether the last character is a vowel. If both conditions are true, then that string qualifies as a vowel string.
To arrive at this solution, it's clear that you must visit each string within the given index range; hence, a loop or iterator is necessary. Within the loop, you need to examine the specific characters of the string - only the first and last characters since these are the ones that determine if a string is a vowel string according to the problem definition.
The use of the Python slicing notation words[left:right+1]
simplifies accessing the sub-array we're interested in. The sum
function is a concise way to count the number of True
evaluations, thereby providing us the total count of vowel strings. By using a generator expression, it performs the check and counts in a single line without the need for an explicit loop or additional variables for counting.
Thus, the approach is to execute the steps as a single inline operation that efficiently traverses the relevant subset of strings and tallies those that meet the vowel string criteria.
Solution Approach
The implementation of the Reference Solution Approach leans on a simple but effective strategy. It is a simulation of the conditions directly stated in the problem description with a healthy usage of Python's expressive syntax and built-in functions.
Here's a step-by-step description of how the solution works:
-
Slicing: The first operation is to slice the
words
array to obtain the relevant sub-array. This is done using the Python slicing syntaxwords[left:right+1]
. Theleft:right+1
slice notation selects all the elements from indexleft
up to and including the indexright
. -
Generator Expression: Next, a generator expression is used to iterate over each word in the sliced sub-array of
words
. Generator expressions are a compact and memory-efficient way to work with sequences in Python. They allow for iterating over data without creating an intermediate list in memory, which would be the case if a list comprehension was used. -
Conditional Check: During the iteration, the condition that each word
w
starts with a vowel (w[0] in 'aeiou'
) and ends with a vowel (w[-1] in 'aeiou'
) is checked. Thew[0]
andw[-1]
syntax accesses the first and last characters of the stringw
, respectively. Thein 'aeiou'
part checks if a given character is among the characters 'a', 'e', 'i', 'o', 'u'. -
Summation: Finally, the
sum()
function wraps the generator expression.sum
adds up theTrue
(which count as 1) evaluations of the conditional checks for every word in the sliced array. SinceFalse
is equivalent to 0, only theTrue
cases contribute to the sum. The result is the count of all strings that are vowel strings within the given index range.
No additional data structures are used as this approach operates directly on the input data and produces the sum immediately, following an efficient memory and time usage pattern.
Here's a bit of code from the solution which encapsulates the process:
1return sum(
2 w[0] in 'aeiou' and w[-1] in 'aeiou' for w in words[left : right + 1]
3)
Each w
represents a string within the specified range. The in
keyword is used twice to perform the vowel checks, and the and
keyword connects the two conditions. Only when both conditions are satisfied does the expression evaluate to True
, subsequently increasing the sum total. This neat inline loop-and-check code effectively solves the problem in an idiomatic and Pythonic way.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example to illustrate the solution approach described above. Suppose we have an array of strings and we want to count the number of vowel strings within a specified range of indices:
words
= ["apple", "banana", "anaconda", "eagle", "kiwi", "onion", "ubi", "orange"]
Let's say left = 2
and right = 5
. The sub-array we need to evaluate is from index 2 to index 5, which includes the words: ["anaconda", "eagle", "kiwi", "onion"]. Now, let's apply the solution step by step:
-
Slicing: We slice the
words
array usingwords[left:right+1]
, which results in ["anaconda", "eagle", "kiwi", "onion"]. -
Generator Expression: Using the generator expression, we iterate over each word in this sliced sub-array.
-
Conditional Check:
- "anaconda": Starts with 'a' and ends with 'a', both of which are vowels. Hence, this word satisfies the condition.
- "eagle": Starts with 'e' and ends with 'e', both vowels. This word satisfies the condition.
- "kiwi": Starts with 'k' and ends with 'i'. Since 'k' is not a vowel, this word does not satisfy the condition.
- "onion": Starts with 'o' and ends with 'n', and 'n' is not a vowel. This word also does not satisfy the condition.
-
Summation: The expression will evaluate to
True
for "anaconda" and "eagle", resulting in a count of 2. For "kiwi" and "onion", the expression evaluates toFalse
.
Therefore, according to our generator expression, we have:
1sum(
2 w[0] in 'aeiou' and w[-1] in 'aeiou' for w in ["anaconda", "eagle", "kiwi", "onion"]
3)
The sum would be calculated as 1 + 1 + 0 + 0 = 2
. Hence, there are 2 vowel strings in the array within the range of indices 2 to 5.
The inline code for this example simply counts the occurrences where both conditions are met and provides us with the final answer. In this case, the function call would look like this:
1count_vowel_strings(words, 2, 5)
And it would return 2
, which is exactly the number of strings that start and end with a vowel in the specified range.
Solution Implementation
1# Import the List type from the typing module to enable type annotations for lists
2from typing import List
3
4class Solution:
5 def vowelStrings(self, words: List[str], left: int, right: int) -> int:
6 # Initialize a counter for the number of strings that meet the criteria.
7 number_of_vowel_strings = 0
8
9 # Loop through the slice of the words list starting from `left` and ending with `right` (inclusive).
10 for word in words[left:right + 1]:
11 # Check if the first and last characters of word are both vowels.
12 if word[0] in 'aeiou' and word[-1] in 'aeiou':
13 # If they are, increment the counter.
14 number_of_vowel_strings += 1
15
16 # Return the total count of strings that start and end with a vowel.
17 return number_of_vowel_strings
18
1class Solution {
2 // Method to count words with vowels at start and end positions within a given range
3 public int vowelStrings(String[] words, int left, int right) {
4 // Initialize the answer to count valid words
5 int validWordCount = 0;
6
7 // Iterate over the specified range in the array
8 for (int i = left; i <= right; ++i) {
9 String word = words[i]; // Current word being checked
10 // Check if both the first and last characters of the word are vowels
11 if (isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1))) {
12 // Increment the count of valid words
13 ++validWordCount;
14 }
15 }
16
17 // Return the count of valid words
18 return validWordCount;
19 }
20
21 // Helper method to check if a character is a vowel
22 private boolean isVowel(char character) {
23 // Check for all lowercase vowels (this code assumes input will be in lowercase)
24 return character == 'a' || character == 'e' || character == 'i' || character == 'o' || character == 'u';
25 }
26}
27
1class Solution {
2public:
3 // Function to count strings in a vector of strings where each string
4 // starts and ends with a vowel.
5 // The function checks elements from index 'left' to 'right' (inclusive).
6 int vowelStrings(vector<string>& words, int left, int right) {
7 // Lambda function to check whether a character is a vowel
8 auto isVowel = [](char c) -> bool {
9 return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
10 };
11
12 // Initialize count of valid strings to 0
13 int validStringCount = 0;
14
15 // Iterate over the specified range of indices
16 for (int i = left; i <= right; ++i) {
17 // Get the current word
18 auto currentWord = words[i];
19
20 // Increment count if the first and last characters of the current word are vowels.
21 validStringCount += isVowel(currentWord[0]) && isVowel(currentWord[currentWord.size() - 1]);
22 }
23
24 // Return the total count of strings starting and ending with a vowel
25 return validStringCount;
26 }
27};
28
1function vowelStrings(words: string[], left: number, right: number): number {
2 // Initialize ans variable to hold the count of strings meeting the condition.
3 let ans = 0;
4 // Define the array of vowel characters for easy checking.
5 const vowels: string[] = ['a', 'e', 'i', 'o', 'u'];
6 // Iterate over the specified range of indices from left to right inclusive.
7 for (let i = left; i <= right; ++i) {
8 // Get the current word to check based on the index.
9 const currentWord = words[i];
10 // Check if the first and last characters of the current word are vowels.
11 if (vowels.includes(currentWord[0]) && vowels.includes(currentWord[currentWord.length - 1])) {
12 // Increment the count if both the first and last characters are vowels.
13 ++ans;
14 }
15 }
16 // Return the total count of strings that start and end with a vowel.
17 return ans;
18}
19
Time and Space Complexity
The time complexity of the provided function vowelStrings
is O(m)
, where m
is the number of elements processed by the sum operation, calculated by the given range right - left + 1
. The function iterates through each element in the slice words[left : right + 1]
once to compute the sum, resulting in a linear relationship between the number of elements and the time taken, hence O(m)
.
The space complexity of the code is O(1)
as there are no additional data structures used that grow with the size of the input. The variables used in the list comprehension within the sum function do not require extra space that depends on the size of the input list, thus it remains constant regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.