2559. Count Vowel Strings in Ranges LeetCode Solution
In this guide, you will get 2559. Count Vowel Strings in Ranges LeetCode Solution with the best time and space complexity. The solution to Count Vowel Strings in Ranges problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Vowel Strings in Ranges
You are given a 0-indexed array of strings words and a 2D array of integers queries.
Each query queries[i] = [li, ri] asks us to find the number of strings present at the indices ranging from li to ri (both inclusive) of words that start and end with a vowel.
Return an array ans of size queries.length, where ans[i] is the answer to the ith query.
Note that the vowel letters are ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’.
Example 1:
Input: words = [“aba”,”bcb”,”ece”,”aa”,”e”], queries = [[0,2],[1,4],[1,1]]
Output: [2,3,0]
Explanation: The strings starting and ending with a vowel are “aba”, “ece”, “aa” and “e”.
The answer to the query [0,2] is 2 (strings “aba” and “ece”).
to query [1,4] is 3 (strings “ece”, “aa”, “e”).
to query [1,1] is 0.
We return [2,3,0].
Example 2:
Input: words = [“a”,”e”,”i”], queries = [[0,2],[0,1],[2,2]]
Output: [3,2,1]
Explanation: Every string satisfies the conditions, so we return [3,2,1].
1 <= words.length <= 105
1 <= words[i].length <= 40
words[i] consists only of lowercase English letters.
sum(words[i].length) <= 3 * 105
1 <= queries.length <= 105
0 <= li <= ri < words.length
Complexity Analysis
Time Complexity: O(|\texttt{words}| + q)
Space Complexity: O(|\texttt{words}|)
2559. Count Vowel Strings in Ranges LeetCode Solution in C++
class Solution {
public:
vector<int> vowelStrings(vector<string>& words,
vector<vector<int>>& queries) {
vector<int> ans;
// prefix[i] := the number of the first i words that start with and end in a
// vowel
vector<int> prefix(words.size() + 1);
for (int i = 0; i < words.size(); ++i)
prefix[i + 1] += prefix[i] + startsAndEndsWithVowel(words[i]);
for (const vector<int>& query : queries) {
const int l = query[0];
const int r = query[1];
ans.push_back(prefix[r + 1] - prefix[l]);
}
return ans;
}
private:
bool startsAndEndsWithVowel(const string& word) {
return isVowel(word.front()) && isVowel(word.back());
}
bool isVowel(char c) {
static constexpr string_view kVowels = "aeiou";
return kVowels.find(c) != string_view::npos;
}
}; /* code provided by PROGIEZ */
2559. Count Vowel Strings in Ranges LeetCode Solution in Java
class Solution {
public int[] vowelStrings(String[] words, int[][] queries) {
int[] ans = new int[queries.length];
// prefix[i] := the number of the first i words that start with and end in a vowel
int[] prefix = new int[words.length + 1];
for (int i = 0; i < words.length; ++i)
prefix[i + 1] += prefix[i] + (startsAndEndsWithVowel(words[i]) ? 1 : 0);
for (int i = 0; i < queries.length; ++i) {
final int l = queries[i][0];
final int r = queries[i][1];
ans[i] = prefix[r + 1] - prefix[l];
}
return ans;
}
private boolean startsAndEndsWithVowel(final String word) {
return isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1));
}
private boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
} // code provided by PROGIEZ
2559. Count Vowel Strings in Ranges LeetCode Solution in Python
class Solution:
def vowelStrings(
self,
words: list[str],
queries: list[list[int]],
) -> list[int]:
kVowels = 'aeiou'
# prefix[i] := the number of the first i words that start with and end in a vowel
prefix = [0] * (len(words) + 1)
for i, word in enumerate(words):
prefix[i + 1] += prefix[i] + (word[0] in kVowels and word[-1] in kVowels)
return [prefix[r + 1] - prefix[l]
for l, r in queries] # code by PROGIEZ
