Problem

You are given a 0-indexed array of strings words and a 2D array of integers queries.

Each query queries[i] = [li, ri] asks us to find the number of strings present in the range li to ri (both inclusive) of words that start and end with a vowel.

Return an arrayans of sizequeries.length , whereans[i]is the answer to theith query.

Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.

Examples

Example 1:

1
2
3
4
5
6
7

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
Output: [2,3,0]
Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
The answer to the query [0,2] is 2 (strings "aba" and "ece").
to query [1,4] is 3 (strings "ece", "aa", "e").
to query [1,1] is 0.
We return [2,3,0].

Example 2:

1
2
3

Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
Output: [3,2,1]
Explanation: Every string satisfies the conditions, so we return [3,2,1].

Constraints:

  • 1 <= words.length <= 105
  • 1 <= words[i].length <= 40
  • words[i] consists only of lowercase English letters.
  • sum(words[i].length) <= 3 * 105
  • 1 <= queries.length <= 105
  • 0 <= li <= ri < words.length

Solution

We need to determine the number of strings that start and end with a vowel for each given query.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

A direct approach is to iterate through each query and count the valid strings in the specified range.

Here is the approach:

  1. Iterate over Queries: For each query, iterate through the range of words specified and count how many meet the condition.
  2. Return Result: Collect answers for all queries and return them.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    private boolean isVowel(char c) {
        return "aeiou".indexOf(c) != -1;
    }
    
    private boolean isVowelStartEnd(String word) {
        return isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1));
    }
    
    public int[] vowelStrings(String[] words, int[][] queries) {
        int[] ans = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int count = 0;
            for (int j = l; j <= r; j++) {
                if (isVowelStartEnd(words[j])) {
                    count++;
                }
            }
            ans[i] = count;
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        def is_vowel(c: str) -> bool:
            return c in 'aeiou'
        
        def is_vowel_start_end(word: str) -> bool:
            return is_vowel(word[0]) and is_vowel(word[-1])
        
        ans: List[int] = []
        for l, r in queries:
            count = sum(1 for word in words[l:r+1] if is_vowel_start_end(word))
            ans.append(count)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n * q), where q is the number of queries, and n is number of words. As for each query, we might need to scan the entire range specified, leading to O(n * q) 
  • 🧺 Space complexity: O(1)

Method 2 - Using Prefix Sum

To efficiently solve the problem, we can pre-calculate the number of strings that start and end with a vowel up to each index and store these counts in an array. This technique allows us to answer any query in constant time (O(1)).

Using a prefix sum array, we store the cumulative count of vowel-strings up to any given index i. For any range (i, j), the number of valid strings can be quickly found using the formula: $$ \text{result} = \text{prefix}[j] - \text{prefix}[i-1] $$

This approach transforms the problem, enabling us to quickly answer queries about any specified range without repeatedly counting, thus improving efficiency.

Approach

  1. We use a prefix sum array, where each element at index i stores the total number of vowel-strings from the start up to index i-1.

    • For eg. for ["aba","bcb","ece","aa","e"] for input array, we check if they start with vowel and end with it ⇨ [1, 0, 1, 1, 1] (1 means it starts and end with vowel)
    • and prefix sum will be [0, 1, 0, 2, 3, 4]

  2. Then, we run the queries on the prefix sum. For each query[l, r], our answer will be prefixSum[r + 1] - prefixSum[l].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int[] vowelStrings(String[] words, int[][] queries) {
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
        
        int n = words.length;
        int[] prefixSum = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i];
            String word = words[i];
            if (vowels.contains(word.charAt(0)) && vowels.contains(word.charAt(word.length() - 1))) {
                prefixSum[i + 1]++;
            }
        }
        
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            ans[i] = prefixSum[r + 1] - prefixSum[l];
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        
        n = len(words)
        prefix_sum = [0] * (n + 1)
        
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i]
            word = words[i]
            if word[0] in vowels and word[-1] in vowels:
                prefix_sum[i + 1] += 1
        
        ans: List[int] = []
        for l, r in queries:
            ans.append(prefix_sum[r + 1] - prefix_sum[l])
        
        return ans

Complexity

  • ⏰ Time complexity: O(n + q)
  • 🧺 Space complexity: O(n) for using prefix sum array