We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Vowel Strings in Ranges

Number: 2691

Difficulty: Medium

Paid? No

Companies: IBM, Amazon, Microsoft, PayPal

Problem Description

Given a 0-indexed array of strings called words and a list of queries where each query is represented as [l, r], return an array where each element is the count of strings in words between indices l and r (inclusive) that start and end with a vowel. The vowels considered are 'a', 'e', 'i', 'o', and 'u'.

Key Insights

  • Preprocess each word by checking if its first and last character are vowels.
  • Create a prefix sum array to efficiently count valid words in any range.
  • For each query [l, r], the result can be computed in O(1) time as prefix[r + 1] - prefix[l].

Space and Time Complexity

Time Complexity: O(n + q), where n is the number of words and q is the number of queries. Space Complexity: O(n) for storing the prefix sum array.

Solution

We use a prefix sum approach. First, iterate through the words array to check if each word starts and ends with a vowel. Build a prefix sum array where each index i+1 holds the count of valid words up to index i. For a query [l, r], the number of valid words is calculated as prefix[r + 1] - prefix[l]. This allows each query to be answered in constant time after the initial O(n) preprocessing step.

Code Solutions

def count_vowel_strings(words, queries):
    # Define a set of vowels for quick lookup
    vowels = set('aeiou')
    n = len(words)
    # Build a prefix sum array with an extra element (prefix[0] = 0)
    prefix = [0] * (n + 1)
    for i in range(n):
        word = words[i]
        # Check if the word starts and ends with a vowel
        if word[0] in vowels and word[-1] in vowels:
            prefix[i + 1] = prefix[i] + 1
        else:
            prefix[i + 1] = prefix[i]
    # Process each query using the prefix sum array
    result = []
    for l, r in queries:
        result.append(prefix[r + 1] - prefix[l])
    return result

# Example usage:
words = ["aba", "bcb", "ece", "aa", "e"]
queries = [[0,2], [1,4], [1,1]]
print(count_vowel_strings(words, queries))  # Expected output: [2, 3, 0]
← Back to All Questions