Count Vowel Strings in Ranges

How it works

Instead of using a hash set to check vowels, we can use a bitmask. Since there are only 5 vowels and 26 letters, we can represent which characters are vowels using a single integer where bit i is set if the character at position i ('a' + i) is a vowel. Checking if a character is a vowel becomes a simple bitwise AND operation.

Steps

1. Create a bitmask for vowels by setting bits for 'a', 'e', 'i', 'o', 'u'.
2. Build a prefix sum array.
3. For each word:
   • Check if the first character's bit is set in the vowel mask.
   • Check if the last character's bit is set in the vowel mask.
   • If both are true, increment the prefix sum.
4. For each query (l, r):
   • The answer is prefix[r+1] - prefix[l].
5. Return the results.

Complexity

• Time complexity: O(n + m)
• Space complexity:
  • O(n) extra space.
  • O(m) space for the output list.

Where n is the number of words, and m is the number of queries.

Things to watch for

Off-by-One Error in Prefix Sum Query

A classic mistake is using prefix[r] - prefix[l] instead of prefix[r + 1] - prefix[l]. The prefix array is 1-indexed to allow easy range queries, so the right endpoint needs the +1 offset.

Checking Only First or Last Character

A vowel string must start AND end with a vowel. Checking only one condition will count words that should not be included.

Hardcoding Vowels Incorrectly

When using a bitmask or set for vowels, omitting one of the five vowels (a, e, i, o, u) leads to incorrect results. This is especially common when manually constructing the bitmask.

from typing import List

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = sum(1 << (ord(c) - ord('a')) for c in "aeiou")
        prefix = [0]
        for w in words:
            prefix.append(prefix[-1])
            if (1 << (ord(w[0]) - ord('a'))) & vowels and (1 << (ord(w[-1]) - ord('a'))) & vowels:
                prefix[-1] += 1
        return [prefix[r + 1] - prefix[l] for l, r in queries]

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        int vowels = 0;
        for (char c : string("aeiou")) {
            vowels |= (1 << (c - 'a'));
        }

        int n = words.size();
        vector<int> prefix(n + 1);
        for (int i = 0; i < n; i++) {
            int f = words[i][0] - 'a';
            int l = words[i].back() - 'a';
            int isVowel = ((1 << f) & vowels) && ((1 << l) & vowels);
            prefix[i + 1] = prefix[i] + isVowel;
        }

        vector<int> res;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            res.push_back(prefix[r + 1] - prefix[l]);
        }

        return res;
    }
};