algoadvance

Leetcode 2586. Count the Number of Vowel Strings in Range

Problem Statement:

You are given a 0-indexed array of string words and two integers left and right.

A string is called a vowel string if it starts with a vowel (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) and ends with a vowel (‘a’, ‘e’, ‘i’, ‘o’, ‘u’).

Return the number of vowel strings words[i] where left <= i <= right.

Clarifying Questions:

1. Are both left and right inclusive?
   • Yes, the problem specifies that we need to count the vowel strings in the range [left, right] inclusive.
2. What is the maximum length of the words array?
   • This information is not provided in the problem statement, but typical constraints would have us assume that the array could be as large as 10^5 elements.
3. What should be returned if there are no vowel strings in the given range?
   • The function should return 0 in that case.
4. Are left and right guaranteed to be within the bounds of the array?
   • It is implied that left and right will be valid indices within the bounds of the array.

Strategy:

1. Initialization:
   • Initialize a counter to keep track of the number of vowel strings.
2. Vowel Set:
   • Create a set of vowels for quick lookup.
3. Iterate Through the Range:
   • Loop through the indices from left to right (inclusive).
   • For each word, check if it starts and ends with a vowel.
   • Increment the counter for each vowel string found.
4. Return the Count:
   • Return the counter after the loop.

Time Complexity:

• Time Complexity: O(N) where N is the number of elements in the range [left, right]. Each check (whether the first and last characters of a string are vowels) is an O(1) operation.
• Space Complexity: O(1) as we’re using a constant amount of extra space for the set of vowels and the counter.

Code:

#include <vector>
#include <string>
#include <unordered_set>

class Solution {
public:
    int countVowelStringsInRange(std::vector<std::string>& words, int left, int right) {
        std::unordered_set<char> vowels {'a', 'e', 'i', 'o', 'u'};
        int count = 0;
        
        for (int i = left; i <= right; ++i) {
            const std::string& word = words[i];
            if (!word.empty() && vowels.count(word.front()) && vowels.count(word.back())) {
                ++count;
            }
        }
        
        return count;
    }
};

In this implementation:

• We use a set of vowels to quickly check if a character is a vowel.
• We loop through the given range [left, right] and check if the first and last characters of each word are in the vowel set.
• We maintain a counter to keep track of the valid vowel strings and return this count at the end.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?