Count Vowel Strings Ranges LeetCode 2559

LeetCode 2559 Count Vowel Strings in Ranges gives you an array of strings words and a 2D array queries where each query is [l, r]. For each query, you must count how many strings in the inclusive range words[l] through words[r] both start with a vowel AND end with a vowel. A vowel is one of the five characters: a, e, i, o, u.

A string qualifies if its first character is a vowel AND its last character is a vowel. For a single-character string like "a", both conditions are satisfied simultaneously because the first and last characters are the same character. The query range [l, r] is inclusive on both ends, so words[l] and words[r] are both included in the count.

The number of strings can be up to 100,000 and the number of queries up to 100,000 as well. A brute-force approach — scanning every word in [l, r] for each query — would be O(q*n) in the worst case, which is up to 10 billion operations. The efficient solution uses prefix sums to answer every query in O(1) after an O(n) preprocessing step.

The key insight is to convert the word array into a boolean array isVowelString[] where isVowelString[i] = 1 if words[i] starts and ends with a vowel, and 0 otherwise. Once you have this binary array, counting how many qualifying strings fall in a range [l, r] becomes a range sum problem — exactly the Range Sum Query pattern (LeetCode 303).

Build a prefix sum array prefix[] of length n+1 where prefix[0] = 0 and prefix[i] = prefix[i-1] + isVowelString[i-1]. This means prefix[i] stores the total count of vowel-bounded strings in words[0] through words[i-1]. To answer query [l, r], the answer is simply prefix[r+1] - prefix[l].

The prefix array is built once in O(n) time. Each query is then answered in O(1) by subtracting two prefix values. Total time complexity is O(n + q) where n is the number of words and q is the number of queries. Space complexity is O(n) for the prefix array.

To build the prefix array, first define a vowel set — the characters {a, e, i, o, u}. Then iterate over each word and determine whether its first character and last character are both vowels. A word qualifies if words[i][0] in vowels AND words[i][-1] in vowels (using Python slice notation). Store the boolean as 1 or 0 in isVowelString[i].

Then build the prefix array of size n+1. prefix[0] = 0 always. For each index i from 0 to n-1, set prefix[i+1] = prefix[i] + isVowelString[i]. This builds the cumulative count of vowel-bounded words from left to right. The extra element at position 0 (set to 0) is what makes the range query formula work cleanly without off-by-one errors.

An alternative implementation combines both steps: iterate over words once, and directly compute prefix as you go — prefix[i+1] = prefix[i] + (1 if words[i][0] in vowels and words[i][-1] in vowels else 0). This saves a separate boolean array allocation. Both approaches produce the same result with O(n) time and O(n) space.

With the prefix array built, answering each query [l, r] requires just one subtraction: answer = prefix[r+1] - prefix[l]. The value prefix[r+1] represents the total count of vowel-bounded strings in words[0..r] (inclusive). The value prefix[l] represents the total count in words[0..l-1] (exclusive of l). Their difference gives the count in words[l..r] exactly.

Iterate over all queries and compute the answer for each using this formula. Build an answers array of the same length as queries, and for each index j, set answers[j] = prefix[queries[j][1] + 1] - prefix[queries[j][0]]. Return the answers array.

The formula works even for single-element ranges: query [i, i] returns prefix[i+1] - prefix[i], which equals isVowelString[i] — exactly 1 if words[i] is vowel-bounded, 0 otherwise. Edge cases for l=0 are also handled correctly because prefix[0] = 0, so the formula returns prefix[r+1] - 0 = prefix[r+1], the full count from the start.

Example: words = ["aba", "bcb", "ece", "aa", "e"], queries = [[0,2], [1,4], [1,1]]. First build isVowelString: "aba" starts with "a" (vowel), ends with "a" (vowel) → 1. "bcb" starts with "b" (not vowel) → 0. "ece" starts with "e" (vowel), ends with "e" (vowel) → 1. "aa" starts with "a" (vowel), ends with "a" (vowel) → 1. "e" starts with "e" (vowel), ends with "e" (vowel) → 1.

Build prefix array: prefix[0]=0, prefix[1]=0+1=1, prefix[2]=1+0=1, prefix[3]=1+1=2, prefix[4]=2+1=3, prefix[5]=3+1=4. So prefix = [0, 1, 1, 2, 3, 4].

Answer queries: query [0,2] → prefix[3] - prefix[0] = 2 - 0 = 2 (strings "aba" and "ece"). Query [1,4] → prefix[5] - prefix[1] = 4 - 1 = 3 (strings "ece", "aa", "e"). Query [1,1] → prefix[2] - prefix[1] = 1 - 1 = 0 (string "bcb" is not vowel-bounded). Answer = [2, 3, 0].

Python solution: def vowelStrings(words, queries): vowels = set("aeiou"); prefix = [0] * (len(words) + 1); for i, w in enumerate(words): prefix[i+1] = prefix[i] + (1 if w[0] in vowels and w[-1] in vowels else 0); return [prefix[r+1] - prefix[l] for l, r in queries]. The list comprehension at the end answers all queries in one readable line. Using w[-1] accesses the last character in Python, which works correctly for any string length including single characters.

Java solution: public int[] vowelStrings(String[] words, int[][] queries) { Set<Character> vowels = Set.of('a','e','i','o','u'); int n = words.length; int[] prefix = new int[n + 1]; for (int i = 0; i < n; i++) { char first = words[i].charAt(0); char last = words[i].charAt(words[i].length() - 1); prefix[i+1] = prefix[i] + (vowels.contains(first) && vowels.contains(last) ? 1 : 0); } int[] ans = new int[queries.length]; for (int j = 0; j < queries.length; j++) ans[j] = prefix[queries[j][1]+1] - prefix[queries[j][0]]; return ans; }.

Both solutions run in O(n + q) time and O(n) space (prefix array). The vowel set lookup is O(1) for a fixed 5-element set. The Python version takes advantage of negative indexing for the last character; the Java version uses words[i].length() - 1. These are the only language-specific details — the algorithm is identical.

Range Sum Query — Immutable (LeetCode 303) is the direct ancestor of this problem. LeetCode 303 asks for range sums over an integer array across multiple queries — the same prefix sum technique with numbers instead of booleans. Solving LeetCode 303 first gives you the exact mental model needed for LeetCode 2559: build prefix once, answer each query in O(1).

Find Pivot Index (LeetCode 724) uses prefix sums from both directions to identify the index where left sum equals right sum. It is a good next step for understanding how prefix arrays can encode running totals and enable complex comparisons in O(n). The same prefix[i+1] = prefix[i] + value[i] recurrence appears in both problems.

Subarray Sum Equals K (LeetCode 560) extends prefix sums with a hash map to count subarrays with a given sum — the most powerful form of the prefix sum pattern. Count Vowel Strings in Ranges (LeetCode 2559) is simpler: you know both endpoints of each query, so no hash map is needed. Together these problems define the prefix sum query family: LeetCode 303 → 2559 → 724 → 560, each adding a layer of technique.