Cho mảng các chuỗi words, một chuỗi được gọi là chuỗi nguyên âm nếu ký tự đầu và cuối đều là nguyên âm (a, e, i, o, u). Với mỗi truy vấn [l, r], đếm xem có bao nhiêu chuỗi nguyên âm trong words[l..r] (bao gồm cả hai đầu).

Bài học kỹ thuật. Đây là mẫu truy vấn phạm vi kinh điển — bạn gặp nó ở dashboard, analytics, mọi nơi làm tổng hợp dữ liệu. Vòng lặp "duyệt theo từng khoảng cho mỗi truy vấn" thì đúng nhưng chậm khi cả mảng lẫn số truy vấn đều chạm 10^5. Prefix sum tính tổng tích lũy một lần, nên mọi câu trả lời phạm vi chỉ còn là một phép trừ. Nếu chỉ nhớ được một kỹ thuật từ bài này, hãy nhớ kỹ thuật đó.

Ý tưởng

Mỗi chuỗi hoặc là chuỗi nguyên âm hoặc không — nên ta có thể thu gọn words thành mảng 0 và 1. Câu hỏi trở thành: "tính tổng giữa hai chỉ số", đúng trường hợp sử dụng kinh điển của prefix sum.

Ví dụ, prefix sum của [1, 2, 3, 4, 5] là [0, 1, 3, 6, 10, 15], với prefix[i] = prefix[i-1] + nums[i]. Tổng từ s đến e bằng prefix[e+1] - prefix[s].

Tại sao có số 0 đầu tiên? Để prefix[e+1] - prefix[s] hoạt động khi s = 0, không cần xử lý riêng.

Cách tiếp cận

  1. Tạo một Set các nguyên âm để tra cứu O(1).
  2. Xây prefixSum, trong đó prefixSum[i] là số chuỗi nguyên âm trong i chuỗi đầu tiên.
  3. Với mỗi truy vấn [l, r], trả lời bằng prefixSum[r+1] - prefixSum[l].
function vowelStrings(words: string[], queries: number[][]): number[] {
  const vowelSet = new Set(["a", "e", "i", "o", "u"]);
 
  const prefixSum: number[] = [0];
  for (const word of words) {
    const isVowelString =
      vowelSet.has(word[0]) && vowelSet.has(word[word.length - 1]);
    prefixSum.push(prefixSum[prefixSum.length - 1] + (isVowelString ? 1 : 0));
  }
 
  return queries.map(([start, end]) => prefixSum[end + 1] - prefixSum[start]);
}

Độ phức tạp

  • Thời gian: O(n + m) — một lần để xây prefix sum (n chuỗi), rồi O(1) cho mỗi truy vấn (m truy vấn).
  • Bộ nhớ: O(n) — cho mảng prefix sum.

Bài học

Trước khi viết vòng lặp lồng nhau, hãy hỏi: truy vấn có lặp lại và độc lập không? Nếu có, hãy tính trước. Prefix sum là thành viên đơn giản nhất của một họ bao gồm prefix sum 2D, mảng sai phân và Fenwick tree — tất cả cùng một ý tưởng: trả trước một lần, trả lời truy vấn tức thì.