Count Vowel Strings in Ranges

main.md

Question

Approaches

Approach 1

My first approach was to map out the vowel list [a, e, i, o, u]. Then I have a res variable to store the results.

Then to check for each range in the queries list, I then extracted the ranges into li and r1 and a count variable to keep track of eligible vowels. Then I iterate with l1 and r1. For each index, I get the corresponding word words[i]. Then I do a check to know if the word starts with a vowel by comparing the first and last words against my vowel_list. Then I increase the count variable if they're satisfied. After this, I append the the count to rhe res variable. When all the queries have now been processed, return the res variable.

Yes, this works. But it's not effiecient as I got a TLE on my solution.

Implementation

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowel_list = ["a", "e", "i", "o", "u"]
        res = []

        for query in queries:
            li, ri = query
            count = 0

            for i in range(li, ri + 1):
                word = words[i]

                if word[0] in vowel_list and word[-1] in vowel_list:
                    count += 1
            
            res.append(count)
            
        return res

Complexities

• Time: O(m * n) where m is the number of queries and n is the number of words in the array.
• Space: O(m) where m is the number of queries.

Approach 2

In this approach, I used set for my vowel_list lookup and a using a prefix sum array. This avoids repeatedly iterating over the same ranges

First, I created a vowel_list containing all the vowels (a, e, i, o, u). Then, I created a valid_vowels array where each element corresponds to whether a word in the words list starts and ends with a vowel. If a word meets the condition, the value at the corresponding index in the valid_vowels array is 1; otherwise, it's 0. Next, I built a prefix sum array from the valid_vowels array. This array stores the counts of valid strings up to each index. For example, prefix[i] represents the count of valid strings in the range 0 to i.

After precomputing the prefix sum, I processed each query in the queries list. For each query, I extracted the range li and ri. Using the prefix sum array, I calculated the number of valid strings in the range [li, ri] in (O(1)) by subtracting the appropriate values:

• If li > 0, the count is prefix[ri] - prefix[li - 1].
• Otherwise, the count is simply prefix[ri].

Finally, I appended the computed count to the res list for each query. After processing all the queries, I returned the res list as the result.

Will I optimize further? For now, no. Maybe when I come back to the question again.

Implementation

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

        n = len(words)

        valid_vowels = [1 if word[0] in vowel_list and word[-1] in vowel_list else 0 for word in words]

        prefix = [0] * n
        prefix[0] = valid_vowels[0]

        for i in range(1, n):
            prefix[i] = prefix[i - 1] + valid_vowels[i]

        for li, ri in queries:
            if li == 0:
                res.append(prefix[ri])
            else:
                res.append(prefix[ri] - prefix[li - 1])
            
        return res

Complexities

• Time: O(n + m) where where n is the length of words and m is is the number of queries.
• Space: O(n + m)