#2586

Easy

LeetCode Problem Workspace

Count the Number of Vowel Strings in Range

Count the Number of Vowel Strings in Range asks to count vowel strings in a subarray of a given word list.

Problem Statement

You are given a 0-indexed array of strings 'words' and two integers 'left' and 'right'. A string is considered a vowel string if it starts and ends with a vowel character, where vowel characters are 'a', 'e', 'i', 'o', and 'u'.

Your task is to return the number of vowel strings within the range [left, right], inclusive, from the given array.

Examples

Example 1

Input: words = ["are","amy","u"], left = 0, right = 2

Output: 2

"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

"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 Approach

Iterating through the range

Start by iterating over the subarray from the 'left' index to the 'right' index. For each string, check if it starts and ends with a vowel.

Checking the first and last characters

For each word in the subarray, verify if the first and last characters are both vowels. If so, count it as a vowel string.

Returning the count

Once all the strings in the range are checked, return the total count of vowel strings found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of strings in the range. Each string takes constant time to check its first and last character. The space complexity is O(1) if we only use a counter, as no extra space is needed beyond the input list.

What Interviewers Usually Probe

Candidate should focus on correct string boundary checks.
Efficiency should be discussed, especially for larger input sizes.
Look for understanding of how the 'left' and 'right' bounds limit the solution scope.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly check the first and last characters of the string.
Not handling edge cases like very short strings or strings that do not have vowels at both ends.
Ignoring array boundaries and accidentally accessing indices outside the given range.

Follow-up variants

What if the strings are larger or the input size increases significantly?
Can this solution be optimized to handle additional constraints?
How would you handle a situation where the 'left' and 'right' range values are the same?

FAQ

How do I count the vowel strings in the range?

Iterate over the specified subarray and check if each word starts and ends with a vowel.

What qualifies as a vowel string?

A vowel string is one that both starts and ends with a vowel ('a', 'e', 'i', 'o', 'u').

How does the 'left' and 'right' range affect the solution?

The 'left' and 'right' indices define the subarray where you need to count the vowel strings.

What are the constraints for this problem?

The array length is between 1 and 1000, and each word has a length between 1 and 10.

How does GhostInterview help with this problem?

GhostInterview helps by providing clarity on boundary checks and offers suggestions for handling larger inputs.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

class Solution:
    def vowelStrings(self, words: List[str], left: int, right: int) -> int:
        return sum(
            w[0] in 'aeiou' and w[-1] in 'aeiou' for w in words[left : right + 1]
        )

Continue Practicing

#2506 count pairs of similar strings #2416 sum of prefix scores of strings #2284 sender with largest word count