# 02.01.2025 [2559. Count Vowel Strings in Ranges]

Count words[q[0]..q[1]] starting and ending with "aeiou" #medium

02.01.2025

2559. Count Vowel Strings in Ranges medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/852

Problem TLDR

Count words[q[0]..q[1]] starting and ending with "aeiou" #medium

Intuition

The prefix sum will answer to each query in O(1) time.

Approach

• to check vowels, we can use a HashSet, bitmask or just a String

• in some languages bool can be converted to int

Complexity

• Time complexity: $$O(n)$$

• Space complexity: $$O(n)$$

Code

    fun vowelStrings(words: Array<String>, queries: Array<IntArray>): List<Int> {
        val fr = IntArray(words.size + 1); val wv = "aeiou"
        for ((i, w) in words.withIndex()) fr[i + 1] = fr[i] + 
            if (w[0] in wv && w.last() in wv) 1 else 0
        return queries.map { (f, t) -> fr[t + 1] - fr[f] }
    }

    pub fn vowel_strings(words: Vec<String>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let mut fr = vec![0; words.len() + 1]; let wv = |b| 1065233 >> (b - b'a') & 1;
        for (i, w) in words.iter().map(|w| w.as_bytes()).enumerate() {
            fr[i + 1] = fr[i] + wv(w[0]) * wv(w[w.len() - 1])
        }
        queries.iter().map(|q| fr[q[1] as usize + 1] - fr[q[0] as usize]).collect()
    }

    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        unordered_set<char> vw({'a', 'e', 'i', 'o', 'u'}); vector<int> f(1), res;
        for (auto &w: words) f.push_back(f.back() + (vw.count(w.front()) && vw.count(w.back())));
        for (auto &q: queries) res.push_back(f[q[1] + 1] - f[q[0]]);
        return res;
    }