ข้อ 15 · LC1456 Maximum Number of Vowels in a Substring of Given Length (นับสระในหน้าต่าง k) 🟡

โจทย์ (LC1456): กำหนด string s และเลขจำนวนเต็ม k ให้หาจำนวน vowel (สระในภาษาอังกฤษ: a, e, i, o, u) ที่มากที่สุด ที่สามารถปรากฏได้ใน substring ใด ๆ ของ s ที่มีความยาวเท่ากับ k พอดี

แนวทาง — ต้องใช้อะไร & คิดยังไง

ใช้ Sliding Window ขนาดคงที่ k เหมือนข้อก่อน แต่แทนที่จะเก็บผลรวม เรา track "จำนวน vowel ใน window" แทน เช็คว่าตัวอักษรเป็นสระด้วย set("aeiou") (hash set) ทำให้เช็คได้ O(1)

brute force นับสระใหม่ในทุก substring ยาว k เป็น O(nk) ช้า Sliding Window เก็บ count แล้วปรับทีละหนึ่งตอนเลื่อน จึงเหลือ O(n)

1. เตรียม set ของสระ นับสระใน window แรก s[:k] เก็บใน count แล้ว initialize best = count
2. iterate i จาก k ไปจนจบ string
3. ถ้าตัวใหม่ s[i] เป็นสระ count += 1
4. ถ้าตัวเก่า s[i - k] เป็นสระ count -= 1
5. update best = max(best, count)
6. (ปรับให้เร็ว) ถ้า best == k หยุดได้เลย เพราะสระเยอะสุดใน window ยาว k คือ k

ไล่ทีละสเต็ป

ลองไล่ s = "leetcode", k = 3 window แรก "lee" มีสระ 2 (e, e)

best = 2 ตลอด คืนค่า 2

def max_vowels(s, k):
    vowels = set("aeiou")
    count = sum(1 for c in s[:k] if c in vowels)   # นับสระในหน้าต่างแรก
    best = count
    for i in range(k, len(s)):
        if s[i] in vowels:        # ตัวใหม่เข้าทางขวา
            count += 1
        if s[i - k] in vowels:    # ตัวเก่าหลุดออกทางซ้าย
            count -= 1
        best = max(best, count)
        if best == k:             # เต็มหน้าต่างแล้ว ไม่มีทางมากกว่านี้
            break
    return best

print(max_vowels("abciiidef", 3))  # 3
print(max_vowels("leetcode", 3))   # 2

3
2