algoadvance

You are given a 0-indexed array of strings words and two integers left and right. A string is called a vowel string if it starts with a vowel and ends with a vowel where vowels are ‘a’, ‘e’, ‘i’, ‘o’, ‘u’. Return the number of vowel strings words[i] where left <= i <= right.

Clarifying Questions

1. What are the length constraints on the words array and the individual strings?
   • The words array can have a length up to 10^4, and each string in words can have a length up to 10^5.
2. What should we consider as vowels?
   • The vowels are ‘a’, ‘e’, ‘i’, ‘o’, ‘u’.
3. Are the indices left and right guaranteed to be within the valid range of the array?
   • Yes, it is guaranteed that 0 <= left <= right < len(words).
4. What should be returned if no strings are within the specified range or if no vowel strings are found within that range?
   • Return 0 in those cases.

Strategy

1. Initialization: Start a counter to keep track of the number of vowel strings.
2. Iteration: Iterate through the subarray words[left:right+1].
3. Check Vowel Strings: For each string in this subarray:
   • Check if the first and last character are vowels.
   • If both are vowels, increment the counter.
4. Return Result: After iterating through the subarray, return the counter.

Code

def is_vowel(c):
    return c in 'aeiou'

def count_vowel_strings(words, left, right):
    count = 0
    for i in range(left, right + 1):
        word = words[i]
        if word and is_vowel(word[0]) and is_vowel(word[-1]):
            count += 1
    return count

# Example usage:
words = ["apple", "banana", "ace", "icicle", "orange"]
left = 1
right = 3
print(count_vowel_strings(words, left, right))  # Should output 1 (only "ace" is a vowel string)

Time Complexity

• Time Complexity: The function iterates through the subarray from left to right, and for each string in this range, it performs a constant-time operation to check the first and last character (if they are vowels). Hence, the time complexity is O(n), where n is the number of strings in the range right - left + 1.
• Space Complexity: The space complexity is O(1) as we are using a fixed amount of additional space for counters and not storing additional data structures proportional to the input size.

This solution is efficient given the problem constraints and should perform well for the upper limits.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?