LeetCode 2559 - Count Vowel Strings in Ranges

LeetCode Problem 2559

Difficulty: 🟡 Medium
Topics: Array, String, Prefix Sum

Solution

Problem Understanding

The problem gives us an array of strings called words and a list of range queries called queries.

For each query [li, ri], we must determine how many strings in words between indices li and ri, inclusive, both start and end with a vowel. The vowels are limited to the lowercase English vowels: 'a', 'e', 'i', 'o', and 'u'.

A string is considered valid if:

• Its first character is a vowel
• Its last character is also a vowel

For example:

• "aba" is valid because it starts with 'a' and ends with 'a'
• "ece" is valid because it starts with 'e' and ends with 'e'
• "bcb" is not valid because it starts with 'b'

The output should be an array where each element corresponds to the answer for one query.

The constraints are important because they strongly influence the algorithm choice:

• words.length can be as large as 10^5
• queries.length can also be as large as 10^5

A naive approach that scans every word inside every query range would become too slow in the worst case. If each query required iterating through nearly the entire array, the total work could reach 10^10 operations, which is far beyond acceptable limits.

The problem guarantees:

• Every string contains only lowercase English letters
• Every string has length at least 1
• Query ranges are always valid, meaning 0 <= li <= ri < words.length

These guarantees simplify implementation because we never need to handle empty strings or invalid indices.

Important edge cases include:

• Arrays where every string is valid
• Arrays where no string is valid
• Queries covering a single index, such as [3,3]
• Very large inputs where efficiency becomes critical
• Strings of length 1, such as "a" or "b"

Single-character strings deserve special attention because the first and last character are the same character. "a" is valid, while "b" is not.

Approaches

Brute Force Approach

The most direct solution is to process every query independently.

For each query [li, ri], we iterate through all words from index li to ri. For every word, we check whether:

• The first character is a vowel
• The last character is a vowel

If both conditions are true, we increment a counter.

This approach is correct because it explicitly checks every candidate string inside the requested range. However, it is inefficient for large inputs.

Suppose:

• n = 100000
• q = 100000

If every query spans almost the entire array, we may perform approximately 10^10 checks.

That is far too slow for competitive programming constraints.

Optimal Approach, Prefix Sum

The key observation is that each word can be independently classified as either:

• Valid, represented as 1
• Invalid, represented as 0

Once we convert the array into binary values, the problem becomes a classic range sum query problem.

For example:

words = ["aba","bcb","ece","aa","e"]

valid = [1,0,1,1,1]

Now the question becomes:

“How many 1s exist between indices li and ri?”

This is exactly what prefix sums solve efficiently.

We build a prefix sum array where:

prefix[i]

stores the number of valid strings among the first i elements.

Then the answer for any range [li, ri] can be computed in constant time:

prefix[ri + 1] - prefix[li]

This reduces total query processing time dramatically.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q × n)	O(1)	Scans every range directly
Optimal	O(n + q)	O(n)	Uses prefix sums for constant-time range queries

Algorithm Walkthrough

1. Create a set containing all vowels.

We use a set because membership lookup is extremely fast, averaging O(1) time complexity.

vowels = {'a', 'e', 'i', 'o', 'u'}

2. Create a prefix sum array of size len(words) + 1.

The extra position at the beginning simplifies range calculations.

prefix[0] = 0

3. Iterate through the words array.

For each word:

• Check whether the first character is a vowel
• Check whether the last character is a vowel

If both conditions are true, mark the word as valid with value 1. Otherwise use 0. 4. Build the prefix sum incrementally.

At index i:

prefix[i + 1] = prefix[i] + valid

This means:

• prefix[i] stores the number of valid words before index i
• prefix[i + 1] includes the current word

5. Process each query.

For query [li, ri], compute:

prefix[ri + 1] - prefix[li]

This subtracts away all valid words before li, leaving only the valid words inside the target range. 6. Store each query result in the answer array. 7. Return the completed answer array.

Why it works

The prefix sum array maintains the invariant that:

prefix[i]

equals the number of valid strings among indices [0, i-1].

Because of this property:

prefix[ri + 1]

contains the number of valid strings from the beginning through ri.

Similarly:

prefix[li]

contains the number of valid strings before li.

Subtracting them isolates exactly the valid strings within [li, ri].

This guarantees correctness for every query.

Python Solution

from typing import List

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

        n = len(words)

        # prefix[i] stores the number of valid words
        # among words[0:i]
        prefix = [0] * (n + 1)

        for i in range(n):
            word = words[i]

            is_valid = (
                word[0] in vowels and
                word[-1] in vowels
            )

            prefix[i + 1] = prefix[i] + (1 if is_valid else 0)

        answer = []

        for left, right in queries:
            count = prefix[right + 1] - prefix[left]
            answer.append(count)

        return answer

The implementation begins by creating a vowel set for fast membership checking.

Next, we allocate a prefix sum array of length n + 1. The additional leading zero allows cleaner range calculations without special handling for ranges beginning at index 0.

The main preprocessing loop checks each word individually. A word is valid if both its first and last characters belong to the vowel set.

The prefix sum array is then updated incrementally. Each position stores the cumulative number of valid words seen so far.

After preprocessing, each query is answered in constant time using the prefix sum formula:

prefix[right + 1] - prefix[left]

Finally, all results are returned as a list.

Go Solution

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

    n := len(words)

    prefix := make([]int, n+1)

    for i := 0; i < n; i++ {
        word := words[i]

        isValid := vowels[word[0]] && vowels[word[len(word)-1]]

        if isValid {
            prefix[i+1] = prefix[i] + 1
        } else {
            prefix[i+1] = prefix[i]
        }
    }

    result := make([]int, 0, len(queries))

    for _, query := range queries {
        left := query[0]
        right := query[1]

        count := prefix[right+1] - prefix[left]

        result = append(result, count)
    }

    return result
}

The Go implementation follows the same algorithmic structure as the Python version.

One notable difference is that Go strings are indexed using bytes. Since the problem guarantees lowercase English letters only, indexing individual bytes is completely safe.

The vowel lookup uses a map[byte]bool for efficient membership testing.

Slices are used naturally for both the prefix sum array and the result array.

Integer overflow is not a concern because the maximum count cannot exceed 10^5, which easily fits inside Go's int type.

Worked Examples

Example 1

words = ["aba","bcb","ece","aa","e"]
queries = [[0,2],[1,4],[1,1]]

First, determine which words are valid.

Index	Word	Starts with vowel?	Ends with vowel?	Valid
0	"aba"	Yes	Yes	1
1	"bcb"	No	No	0
2	"ece"	Yes	Yes	1
3	"aa"	Yes	Yes	1
4	"e"	Yes	Yes	1

Construct the prefix sum array.

i	prefix[i]
0	0
1	1
2	1
3	2
4	3
5	4

Now process queries.

Query [0,2]

prefix[3] - prefix[0]
= 2 - 0
= 2

Query [1,4]

prefix[5] - prefix[1]
= 4 - 1
= 3

Query [1,1]

prefix[2] - prefix[1]
= 1 - 1
= 0

Final answer:

[2,3,0]

Example 2

words = ["a","e","i"]
queries = [[0,2],[0,1],[2,2]]

Determine valid words.

Index	Word	Valid
0	"a"	1
1	"e"	1
2	"i"	1

Build prefix sums.

i	prefix[i]
0	0
1	1
2	2
3	3

Process queries.

Query [0,2]

prefix[3] - prefix[0]
= 3 - 0
= 3

Query [0,1]

prefix[2] - prefix[0]
= 2 - 0
= 2

Query [2,2]

prefix[3] - prefix[2]
= 3 - 2
= 1

Final answer:

[3,2,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + q)	Building prefix sums takes O(n), answering queries takes O(q)
Space	O(n)	The prefix sum array stores n + 1 integers

The preprocessing step scans the words array exactly once. Each query is then answered in constant time using the prefix sum array.

This is significantly more efficient than repeatedly scanning query ranges.

The space complexity comes from the prefix sum array, which stores cumulative counts for all positions.

Test Cases

from typing import List

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

        prefix = [0] * (len(words) + 1)

        for i, word in enumerate(words):
            valid = word[0] in vowels and word[-1] in vowels
            prefix[i + 1] = prefix[i] + (1 if valid else 0)

        result = []

        for left, right in queries:
            result.append(prefix[right + 1] - prefix[left])

        return result

solution = Solution()

# Example 1
assert solution.vowelStrings(
    ["aba", "bcb", "ece", "aa", "e"],
    [[0, 2], [1, 4], [1, 1]]
) == [2, 3, 0]  # standard mixed example

# Example 2
assert solution.vowelStrings(
    ["a", "e", "i"],
    [[0, 2], [0, 1], [2, 2]]
) == [3, 2, 1]  # all strings valid

# No valid strings
assert solution.vowelStrings(
    ["b", "c", "d"],
    [[0, 2], [1, 1]]
) == [0, 0]  # no vowel strings

# Single element valid
assert solution.vowelStrings(
    ["a"],
    [[0, 0]]
) == [1]  # single valid word

# Single element invalid
assert solution.vowelStrings(
    ["z"],
    [[0, 0]]
) == [0]  # single invalid word

# Mixed string lengths
assert solution.vowelStrings(
    ["ae", "abc", "ou", "uii", "bbb"],
    [[0, 4], [1, 3], [2, 2]]
) == [3, 2, 1]  # varying lengths

# Entire array query
assert solution.vowelStrings(
    ["aa", "ee", "ii", "oo", "uu"],
    [[0, 4]]
) == [5]  # whole array

# Multiple small overlapping queries
assert solution.vowelStrings(
    ["aba", "xyz", "ece", "pop", "ii"],
    [[0, 0], [0, 2], [2, 4], [1, 3]]
) == [1, 2, 2, 1]  # overlapping ranges

# Single-character consonants and vowels
assert solution.vowelStrings(
    ["a", "b", "e", "f", "i"],
    [[0, 4], [1, 3]]
) == [3, 1]  # single-character handling

# Large repeated pattern
words = ["aba", "bcb"] * 1000
queries = [[0, 1999], [0, 0], [1, 1]]

assert solution.vowelStrings(
    words,
    queries
) == [1000, 1, 0]  # stress-style repeated input

Test	Why
Mixed valid and invalid strings	Verifies standard functionality
All strings valid	Ensures counting logic works correctly
No valid strings	Ensures zero counts are handled
Single valid element	Tests smallest valid input
Single invalid element	Tests smallest invalid input
Mixed string lengths	Verifies length independence
Entire array query	Tests full-range handling
Overlapping queries	Ensures prefix subtraction works correctly
Single-character words	Verifies first and last character logic
Large repeated pattern	Simulates high-volume input

Edge Cases

Single-Character Strings

A string of length one has the same first and last character. This can easily introduce bugs if the implementation assumes at least two characters.

For example:

"a"

should count as valid because 'a' is both the first and last character.

The implementation handles this naturally because:

word[0] == word[-1]

for single-character strings.

Queries Covering One Element

Queries such as:

[3,3]

must correctly evaluate only one word.

Some incorrect implementations accidentally treat ranges as half-open intervals or introduce off-by-one mistakes.

Using the prefix formula:

prefix[right + 1] - prefix[left]

correctly handles single-index ranges without any special cases.

No Valid Strings

If every string begins or ends with a consonant, every query answer should be zero.

For example:

words = ["b", "cd", "xyz"]

The prefix array remains entirely zero:

[0,0,0,0]

The subtraction logic still works correctly because subtracting equal prefix values produces zero.

Large Inputs

With up to 10^5 words and 10^5 queries, inefficient solutions will time out.

The prefix sum approach avoids repeated scanning by preprocessing once and answering every query in constant time.

This guarantees the solution remains efficient even at maximum input size.