กบ นาก และนกฮูกการ์ตูนถกเถียงกันหน้ากระดานตัวอักษร มีหน้าต่างเลื่อนสีมิ้นต์ครอบช่วงตัวอักษร
leetcodepythonalgorithmssliding-windowbenchmark

LeetCode #424 Longest Repeating Character Replacement: หน้าต่างเลื่อน vs ไล่ทุกช่วง

น้องกายEngineering

โจทย์ Longest Repeating Character Replacement #424 ให้สตริงตัวพิมพ์ใหญ่กับจำนวนครั้ง k ที่เปลี่ยนตัวอักษรได้ ขอช่วงต่อเนื่องที่ยาวที่สุดหลังเปลี่ยนไม่เกิน k ครั้ง เช่น AABABBA กับ k=1 ได้คำตอบ 4

รอบนี้ไม่ใช้พี่โชว์หรือน้องกายเป็นตัวอธิบายครับ ใช้สัตว์สามตัวแทนสามแนวทาง แล้วให้บารอน (สิงโตทะเลใส่โค้ท) ปิดด้วยตัวเลขจากเครื่องนี้

ผู้เข้าแข่งขัน

ตัวละครวิธีนิสัย
กบขี้เกียจไล่ทุกคู่จุดเริ่ม-จบ (brute force)นั่งดูทุกช่วงทีละอัน
นากกายหน้าต่างเลื่อน + นับความถี่ขยับขอบขวา/ซ้ายเท่าที่จำเป็น
นกฮูกแผนที่หน้าต่างเลื่อนแบบจำ max ความถี่จำค่าสูงสุดในหน้าต่าง ไม่รีเซ็ตทุกครั้ง
บารอนกรรมการฟัง benchmark

วิธีที่ 1: กบขี้เกียจ — ไล่ทุกช่วง

ลองทุกจุดเริ่ม i และขยาย j นับตัวที่โผล่บ่อยสุดในช่วง ถ้าความยาวลบความถี่สูงสุดเกิน k ก็หยุดขยาย เวลาแย่สุดประมาณ O(n²·Σ) เมื่อ Σ=26

ข้อดี: อ่านง่าย เหมาะไวท์บอร์ดสั้น
ข้อเสีย: ช้าเมื่อ n ใหญ่

วิธีที่ 2–3: นากและนกฮูก — หน้าต่างเลื่อน

ขยายขอบขวาเสมอ ถ้า (ความยาวหน้าต่าง - ความถี่ตัวที่มากสุด) > k ให้ขยับขอบซ้าย ความยาวที่ดีที่สุดเก็บไว้ตลอด เวลา O(n) พื้นที่ O(1) สำหรับตัวอักษร 26 ตัว

นกฮูกจำ maxf แบบไม่ลดตอนขยับซ้ายได้ เพราะคำตอบสนใจแค่หน้าต่างที่ยาวขึ้น ความถูกต้องยังอยู่

ตารางเลือกใช้

สถานการณ์เลือก
สัมภาษณ์ อธิบายแนวคิดหน้าต่างเลื่อน
n เล็กมาก อยากโค้ดสั้นสุดbrute force ก็ได้
production hot pathหน้าต่างเลื่อน O(n)

Benchmark ที่รันจริง (2026-10-14 บนเครื่องนี้)

สตริงสุ่มยาว 8,000 ตัว จากชุด ABCD, k=2

วิธีเวลาโดยประมาณ
หน้าต่างเลื่อน n=80001.36 ms
brute force n=400 (เทียบสเกล)0.29 ms บนช่วงสั้นกว่ามาก

brute บน n=8000 จะช้าแบบกำลังสอง จึงวัดบน n=400 เพื่อพิสูจน์แนวคิด ไม่ใช่แย่งแชมป์ความเร็ว

ตัวอย่างโค้ด (หน้าต่างเลื่อน)

def character_replacement(s: str, k: int) -> int:
    count = [0] * 26
    left = best = maxf = 0
    for right, ch in enumerate(s):
        i = ord(ch) - 65
        count[i] += 1
        maxf = max(maxf, count[i])
        while (right - left + 1) - maxf > k:
            count[ord(s[left]) - 65] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

assert character_replacement("AABABBA", 1) == 4
assert character_replacement("ABAB", 2) == 4
print("ok")

บารอนสรุป

บารอนบอกว่าบนอินพุตยาว หน้าต่างเลื่อนชนะชัด ถ้าแค่สอนเด็กให้เห็นทุกรูปแบบ ค่อยโชว์ brute บน n เล็ก แล้วย้ายไปเลื่อนหน้าต่าง

Recap

  • โจทย์: ช่วงยาวสุดหลังเปลี่ยนได้ ≤ k ครั้ง
  • Brute O(n²) vs หน้าต่างเลื่อน O(n)
  • จำ: ความยาว − ความถี่สูงสุด ≤ k
  • Benchmark เครื่องนี้: เลื่อนหน้าต่าง ~1.36 ms ที่ n=8000
  • สัมภาษณ์/โปรดักชัน: เลือกเลื่อนหน้าต่างเป็นค่าเริ่มต้น