LeetCode 2586 - Count the Number of Vowel Strings in Range

The problem gives us an array of lowercase strings called words and two integer indices, left and right. We need to count how many strings within the inclusive range [left, right] are considered vowel strings.

leetcodeeasyarraystringcounting

LeetCode Problem 2586

Difficulty: 🟢 Easy
Topics: Array, String, Counting

Solution

Problem Understanding

The problem gives us an array of lowercase strings called words and two integer indices, left and right. We need to count how many strings within the inclusive range [left, right] are considered vowel strings.

A string qualifies as a vowel string if both of these conditions are true:

  1. The first character is a vowel.
  2. The last character is also a vowel.

The valid vowels are:

a, e, i, o, u

The range [left, right] tells us which part of the array we should examine. We do not check every string in the array unless the range covers the entire array.

For example, if:

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

we inspect:

"are", "amy", "u"

The word "are" starts with 'a' and ends with 'e', so it counts. The word "amy" starts with 'a' but ends with 'y', so it does not count. The word "u" starts and ends with 'u', so it counts.

The constraints are small:

  • words.length <= 1000
  • words[i].length <= 10

This tells us that even a straightforward linear scan is efficient enough. We do not need advanced optimization techniques such as prefix sums or preprocessing for this specific problem size.

There are several important edge cases to consider:

  • A word may contain only one character, such as "u". In this case, the same character is both the first and last character.
  • The range may contain exactly one element, where left == right.
  • Some words may start with vowels but end with consonants, or vice versa.
  • The input guarantees all words contain only lowercase English letters, so we do not need to handle uppercase characters.

Approaches

Brute Force Approach

The brute force solution checks every string between indices left and right. For each word, we inspect the first and last characters and determine whether both belong to the vowel set.

This approach is correct because every candidate string in the required range is examined exactly once. If a word satisfies both conditions, we increment the answer counter.

Although this solution is called brute force, it is already efficient enough for the given constraints because the maximum number of words is only 1000.

Key Insight for the Optimal Approach

The key observation is that each word can be validated independently using only its first and last characters.

We do not need to analyze the entire string. Instead:

  • Check word[0]
  • Check word[-1]

If both are vowels, count the word.

Using a hash set for vowels allows constant time membership checking.

Since each word is processed once and each operation is constant time, the overall solution runs in linear time relative to the number of words in the range.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Scan every word in the range and check first and last characters
Optimal O(n) O(1) Same linear scan, optimized using constant time vowel lookup

Here, n represents the number of words in the range [left, right].

Algorithm Walkthrough

  1. Create a set containing all vowels.

We use a set because membership checks are extremely fast, typically O(1). The set will contain:

{'a', 'e', 'i', 'o', 'u'}
  1. Initialize a counter variable to zero.

This variable stores the number of valid vowel strings found so far. 3. Iterate through the array from index left to index right.

We only inspect the required portion of the array because the problem explicitly restricts the counting range. 4. For each word, extract the first and last characters.

The first character is:

word[0]

The last character is:

word[-1]
  1. Check whether both characters are vowels.

If both belong to the vowel set, increment the counter. 6. After processing all words in the range, return the counter.

Why it works

The algorithm works because every word in the required range is checked exactly once against the exact definition of a vowel string. A word is counted if and only if its first and last characters are vowels. Since no valid word is skipped and no invalid word is counted, the final counter is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def vowelStrings(self, words: List[str], left: int, right: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        count = 0

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

            if word[0] in vowels and word[-1] in vowels:
                count += 1

        return count

The implementation begins by creating a set of vowels for fast lookup. The variable count tracks how many valid vowel strings have been found.

The loop iterates only through the indices specified by the range [left, right]. For each word, the code checks whether the first and last characters exist in the vowel set.

If both conditions are true, the counter increases by one.

Finally, the function returns the total count.

Go Solution

func vowelStrings(words []string, left int, right int) int {
    vowels := map[byte]bool{
        'a': true,
        'e': true,
        'i': true,
        'o': true,
        'u': true,
    }

    count := 0

    for i := left; i <= right; i++ {
        word := words[i]

        if vowels[word[0]] && vowels[word[len(word)-1]] {
            count++
        }
    }

    return count
}

The Go implementation follows the same logic as the Python version. A map is used for constant time vowel lookup.

Since strings in Go are byte slices for ASCII characters, we can directly access characters using indexing like:

word[0]

and

word[len(word)-1]

The problem guarantees lowercase English letters only, so byte indexing is completely safe here.

Worked Examples

Example 1

Input:

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

Initial state:

count = 0
vowels = {a, e, i, o, u}
Index Word First Char Last Char Valid? Count
0 "are" a e Yes 1
1 "amy" a y No 1
2 "u" u u Yes 2

Final answer:

2

Example 2

Input:

words = ["hey","aeo","mu","ooo","artro"]
left = 1
right = 4

Initial state:

count = 0
Index Word First Char Last Char Valid? Count
1 "aeo" a o Yes 1
2 "mu" m u No 1
3 "ooo" o o Yes 2
4 "artro" a o Yes 3

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each word in the range is checked once
Space O(1) The vowel set uses constant extra space

The algorithm performs a single pass through the selected range of words. Each iteration performs only constant time operations, specifically checking two characters against a fixed-size set.

The space usage remains constant because the vowel set always contains exactly five characters regardless of input size.

Test Cases

from typing import List

class Solution:
    def vowelStrings(self, words: List[str], left: int, right: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        count = 0

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

            if word[0] in vowels and word[-1] in vowels:
                count += 1

        return count

solution = Solution()

assert solution.vowelStrings(["are","amy","u"], 0, 2) == 2
# Basic example with mixed valid and invalid words

assert solution.vowelStrings(["hey","aeo","mu","ooo","artro"], 1, 4) == 3
# Example with partial array range

assert solution.vowelStrings(["a"], 0, 0) == 1
# Single character vowel word

assert solution.vowelStrings(["b"], 0, 0) == 0
# Single character consonant word

assert solution.vowelStrings(["abc", "ece", "ioi"], 0, 2) == 2
# Multiple valid vowel strings

assert solution.vowelStrings(["aa", "ee", "ii", "oo", "uu"], 0, 4) == 5
# Every word is valid

assert solution.vowelStrings(["ab", "cd", "ef"], 0, 2) == 0
# No valid vowel strings

assert solution.vowelStrings(["aba", "ece", "iki"], 1, 1) == 1
# Range containing exactly one valid word

assert solution.vowelStrings(["apple", "orange", "ice"], 0, 1) == 2
# Only part of the array is considered

assert solution.vowelStrings(["u", "e", "i", "o", "a"], 2, 4) == 3
# Range at the end of the array

Test Summary

Test Why
["are","amy","u"] Validates the basic example
["hey","aeo","mu","ooo","artro"] Validates subrange processing
["a"] Tests single character vowel word
["b"] Tests single character consonant word
["abc", "ece", "ioi"] Tests mixed valid and invalid words
["aa", "ee", "ii", "oo", "uu"] Tests all valid words
["ab", "cd", "ef"] Tests zero valid words
["aba", "ece", "iki"] with range [1,1] Tests single index range
["apple", "orange", "ice"] Tests partial array traversal
["u", "e", "i", "o", "a"] Tests range ending at final index

Edge Cases

One important edge case is a single character word such as "u". Since the word has length one, the first and last characters are the same. A careless implementation might incorrectly assume the word must contain at least two characters. This solution correctly handles the case because both word[0] and word[-1] refer to the same character.

Another important edge case occurs when left == right. In this scenario, the range contains exactly one word. Some implementations accidentally skip processing because they use incorrect loop bounds. This solution uses:

range(left, right + 1)

which correctly includes both endpoints.

A third edge case is when no words qualify as vowel strings. For example:

["ab", "cd", "ef"]

None of these words both start and end with vowels. The implementation handles this naturally because the counter only increases when both conditions are satisfied. If no valid words are found, the initial value 0 is returned unchanged.