2559.count-vowel-strings-in-ranges.md

2559. Count Vowel Strings in Ranges

Prefix Sum (0-Indexed)

private val vowels = hashSetOf('a', 'e', 'i', 'o', 'u')

fun vowelStrings(words: Array<String>, queries: Array<IntArray>): IntArray {
    val isVowels = BooleanArray(words.size)
    for (i in 0 until words.size) {
        val w = words[i]
        isVowels[i] = vowels.contains(w[0]) && vowels.contains(w[w.length - 1])
    }
    
    val prefixSum = IntArray(words.size)
    prefixSum[0] = if (isVowels[0]) 1 else 0
    for (i in 1 until words.size) {
        prefixSum[i] = prefixSum[i - 1] + (if (isVowels[i]) 1 else 0)
    }
    
    val result = IntArray(queries.size)
    for (i in 0 until queries.size) {
        val s = queries[i][0]
        val e = queries[i][1]
        
        val prefixEnd = prefixSum[e]
        val prefixStart = if (s == 0) 0 else prefixSum[s - 1]
        
        result[i] = prefixEnd - prefixStart
    }
    return result
}

• Time Complexity: O(W + Q) where W and Q represent the length of words and queries.
• Space Complexity: O(W + Q).

Prefix Sum (1-Indexed with Sentinel)

Using 1-indexed prefix sum with sentinel prefix[0] = 0 to avoid edge case handling.

private val vowels = hashSetOf('a', 'e', 'i', 'o', 'u')

fun vowelStrings(words: Array<String>, queries: Array<IntArray>): IntArray {
    val n = words.size
    // 1-indexed: prefix[i] = count of vowel strings in words[0..i-1]
    val prefix = IntArray(n + 1)
    for (i in 0 until n) {
        val w = words[i]
        val isVowel = w.first() in vowels && w.last() in vowels
        prefix[i + 1] = prefix[i] + if (isVowel) 1 else 0
    }
    
    return IntArray(queries.size) { i ->
        val (left, right) = queries[i]
        prefix[right + 1] - prefix[left]  // No edge case for left == 0
    }
}

• Time Complexity: O(W + Q) where W and Q represent the length of words and queries.
• Space Complexity: O(W + Q).