Count the Number of Vowel Strings in Range

Easy

PayPal

1 view

Topics:

ArraysStringsTwo Pointers

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

Count the Number of Vowel Strings in Range

Easy

PayPal

1 view

Topics:

ArraysStringsTwo Pointers

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the `words` array and the length of each string within it?
Are `left` and `right` guaranteed to be valid indices within the `words` array (i.e., 0 <= left <= right < words.length)?
Can the input strings contain characters other than lowercase English letters?
Is the vowel check case-sensitive, or should I consider uppercase vowels as well?
If no strings in the given range start and end with a vowel, what should I return (e.g., 0, null, or an empty list)?

Brute Force Solution

Approach

We need to figure out how many words in a list start and end with vowels within a given range. The brute force approach looks at each word individually within that range and directly checks if it meets our criteria.

Here's how the algorithm would work step-by-step:

Look at each word one by one, starting from the first word within the specified range.
For each word, check if the first letter is a vowel (a, e, i, o, u).
If the first letter is not a vowel, move on to the next word.
If the first letter is a vowel, check if the last letter is also a vowel.
If the last letter is not a vowel, move on to the next word.
If both the first and last letters are vowels, count this word as a match.
Repeat this process for every word within the specified range.
After checking all the words in the range, report the total number of matching words we found.

Code Implementation

def count_vowel_strings_in_range_brute_force(words, left, right):
    vowel_count = 0

    for index in range(left, right + 1):
        word = words[index]
        first_character = word[0]
        last_character = word[-1]

        # Check if the first letter is a vowel
        if first_character in 'aeiou':

            # Further check if the last letter is a vowel
            if last_character in 'aeiou':
                vowel_count += 1

    return vowel_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the words array once, from left to right, within the specified range. For each word within the range, it performs a constant number of operations to check if the first and last characters are vowels. Therefore, the time complexity is directly proportional to the number of words in the specified range, resulting in a linear time complexity of O(n), where n is the size of the range (right - left + 1).

Space Complexity

O(1) – The provided algorithm iterates through a range of words but doesn't create any additional data structures that scale with the input size (N, where N is the number of words). It only uses a few constant space variables such as loop counters and boolean flags to check if the first and last characters are vowels. Therefore, the auxiliary space used is constant and does not depend on the number of words or the length of the words.

Optimal Solution

Approach

Instead of checking every word in the specified range, we use a clever mathematical trick. We can quickly calculate the number of vowel strings of a given length starting from 'a' and subtract a similar calculation starting after the given range's end to efficiently obtain the answer.

Here's how the algorithm would work step-by-step:

Recognize that the number of vowel strings of a certain length can be calculated directly using a mathematical formula related to combinations with repetition.
Create a function or method to calculate the number of vowel strings up to a given length when vowels are picked from 'a' to 'u' which are 5 vowels
Calculate the number of vowel strings up to the end position of the range.
Calculate the number of vowel strings up to the position just before the start position of the range.
Subtract the second result from the first to get the number of vowel strings within the specified range.

Code Implementation

def count_vowel_strings(string_length: int) -> int:
    # Use combinatorics: (n+k-1) choose (k-1), where n=5 (vowels), k=string_length
    return (string_length + 4) * (string_length + 3) * (string_length + 2) * (string_length + 1) // 24

def vowel_strings_in_range(words: list[str], left: int, right: int) -> int:
    vowels = "aeiou"
    vowel_string_count = 0

    # Iterate only through the relevant part of the given list
    for i in range(left, right + 1):
        word = words[i]
        # Checks if a word starts and ends with vowels
        if word[0] in vowels and word[-1] in vowels:
            vowel_string_count += 1

    return vowel_string_count

Big(O) Analysis

Time Complexity

O(1) – The provided solution calculates the number of vowel strings using a mathematical formula directly, instead of iterating through strings or vowel combinations. It involves calling a function twice to compute the number of vowel strings up to the end and start indices of the range. Since the computations involve a fixed number of mathematical operations regardless of the input size (length of words array or the range), the time complexity is constant.

Space Complexity

O(1) – The solution calculates the number of vowel strings using a mathematical formula, potentially involving combinations with repetition. This calculation is done with a fixed number of variables regardless of the input range. Therefore, no auxiliary data structures that scale with the input range are used and the space complexity is constant.

Edge Cases

Case	How to Handle
words is null or empty	Return 0 immediately, as there are no strings to process.
left or right are out of bounds (left < 0 or right >= words.length)	Adjust left and right to be within valid bounds of the array (e.g., Math.max(0, left), Math.min(words.length - 1, right)).
left > right	Return 0 immediately, as the range is invalid.
words array contains empty strings	Empty strings do not start or end with vowels, so they should not be counted.
words array contains strings with non-alphabetic characters	The vowel check should only consider alphabetic characters; non-alphabetic characters are irrelevant.
words array contains strings that are all vowels, consonants, or mixed.	The logic should correctly identify vowel strings regardless of the overall distribution of vowels and consonants.
Large words array (performance)	The solution should iterate through the specified range of the array efficiently, with a time complexity of O(n) where n is the number of words in the range.
Strings in words that consist entirely of vowels, or non-vowels	The logic for identifying vowel strings handles strings of any length that begin and end with vowels.