Problem of The Day: Count Ways To Build Good Strings

Problem Statement

Brute Force [TLE]

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        N = len(words)
        arr = [False] * N
        vowels = "aeiou"
        for i, word in enumerate(words):
            if word[0] in vowels and word[-1] in vowels:
                arr[i] = True

        res = [0] * len(queries)
        for i, [l, r] in enumerate(queries):
            res[i] = sum(arr[l:r+1])
        return res

Improved Algorithm

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        N = len(words)
        arr = [0] * N
        vowels = set(['a','e','i','o','u'])
        curr_sum = 0
        for i, word in enumerate(words):
            if word[0] in vowels and word[-1] in vowels:
                curr_sum += 1
            arr[i] = curr_sum

        res = [0] * len(queries)
        for i, [l, r] in enumerate(queries):
            if l - 1 < 0:
                res[i] = arr[r]
            else:
                res[i] = arr[r] - arr[l - 1]
        return res

Editorial

class Solution:
    def vowelStrings(
        self, words: List[str], queries: List[List[int]]
    ) -> List[int]:
        ans = [0] * len(queries)
        vowels = {"a", "e", "i", "o", "u"}
        prefix_sum = [0] * len(words)
        sum = 0
        for i in range(len(words)):
            current_word = words[i]
            if (
                current_word[0] in vowels
                and current_word[len(current_word) - 1] in vowels
            ):
                sum += 1
            prefix_sum[i] = sum

        for i in range(len(queries)):
            current_query = queries[i]
            ans[i] = prefix_sum[current_query[1]] - (
                0 if current_query[0] == 0 else prefix_sum[current_query[0] - 1]
            )

        return ans

• time: O(m + n) where m is size of queries and n is size of words
• space: O(m)