LeetCode Entry

2559. Count Vowel Strings in Ranges

02.01.2025 medium 2025 kotlin rust

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

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

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;
    }