Sliding Window — พื้นฐาน & แนวคิด

Sliding Window (หน้าต่างเลื่อน) คือเทคนิคหาคำตอบของ "ช่วงต่อเนื่อง" ใน array หรือ string เช่น ผลรวมมากสุดของช่วงยาว k, substring ยาวสุดที่ไม่มีตัวซ้ำ, หรือช่วงที่มี 0 ไม่เกิน k ตัว หลักการคือเก็บ window เดียวไว้แล้วเลื่อนขอบทีละก้าว อัปเดตแค่ตัวที่เข้ากับตัวที่ออก แทนที่จะคำนวณทั้งช่วงใหม่ทุกครั้ง

ขอบ window คุมด้วยตัวแปรสองตัว left กับ right — คล้าย two pointers แต่เดินไปทางเดียวกันเสมอ และสิ่งที่สนใจคือทุกอย่างระหว่างสองขอบ ไม่ใช่แค่ค่าปลายสองข้าง

ทำไมต้องมีท่านี้ — ดู brute force ก่อน

ตัวอย่าง: หาผลรวมมากสุดของช่วงยาว k = 3 ใน nums = [2, 1, 5, 1, 3, 2] — brute force คือลองทุกช่วงยาว 3 แล้วบวกใหม่ทุกครั้ง

nums = [2, 1, 5, 1, 3, 2]
k = 3
best = float("-inf")
adds = 0                                   # นับว่าบวกเลขกี่ครั้ง

for i in range(len(nums) - k + 1):         # ทุกจุดเริ่มต้นที่เป็นไปได้
    total = 0
    for j in range(i, i + k):              # บวก k ตัวใหม่ทุกครั้ง
        total += nums[j]
        adds += 1
    best = max(best, total)
    print(f"ช่วง [{i}:{i+k}] = {nums[i:i+k]} รวม = {total}")

print("best =", best, "| บวกไปทั้งหมด", adds, "ครั้ง")

ช่วง [0:3] = [2, 1, 5] รวม = 8
ช่วง [1:4] = [1, 5, 1] รวม = 7
ช่วง [2:5] = [5, 1, 3] รวม = 9
ช่วง [3:6] = [1, 3, 2] รวม = 6
best = 9 | บวกไปทั้งหมด 12 ครั้ง

ช่วงถัดไปซ้อนกับช่วงก่อนเกือบหมด ต่างแค่ตัวซ้ายหลุด ตัวขวาเข้าใหม่ แต่ brute force บวกทั้งก้อนใหม่ทุกครั้ง เมื่อ n และ k ใหญ่ (เช่น n = 10⁵, k = 10⁴) จะกลายเป็น O(nk) ที่รันไม่ทัน

nums = [2, 1, 5, 1, 3, 2]
k = 3
window = sum(nums[:k])                     # สร้างหน้าต่างแรกครั้งเดียว
best = window
ops = k                                    # นับการบวก/ลบ

print(f"เริ่ม   window = {nums[:k]} รวม = {window}")

for i in range(k, len(nums)):
    entering = nums[i]                     # ตัวใหม่เข้าทางขวา
    leaving = nums[i - k]                  # ตัวเก่าหลุดออกทางซ้าย
    window += entering - leaving
    ops += 2
    best = max(best, window)
    print(f"เลื่อน  เข้า {entering}, ออก {leaving} -> รวม = {window}")

print("best =", best, "| บวก/ลบไปทั้งหมด", ops, "ครั้ง")

เริ่ม   window = [2, 1, 5] รวม = 8
เลื่อน  เข้า 1, ออก 2 -> รวม = 7
เลื่อน  เข้า 3, ออก 1 -> รวม = 9
เลื่อน  เข้า 2, ออก 5 -> รวม = 6
best = 9 | บวก/ลบไปทั้งหมด 9 ครั้ง

ได้คำตอบเดียวกัน (best = 9 จาก [5, 1, 3]) แต่งานลดลง และสำคัญกว่านั้นคืองานโตตาม n ไม่ใช่ n×k — นี่คือเหตุผลที่เหลือ O(n)

สองแบบที่ต้องแยกให้ออก: Fixed vs Variable

ทุกโจทย์ sliding window ตกอยู่ในหนึ่งในสองแบบ การตั้งชื่อให้ถูกตั้งแต่แรกคือครึ่งหนึ่งของการแก้

แบบที่ 1 — Fixed-size (ขนาดคงที่)

โจทย์บอกความยาว k มาชัดเจน window ไม่เปลี่ยนขนาด แค่เลื่อนไปทีละ 1: บวกตัวเข้าขวา ลบตัวออกซ้าย ใช้เมื่อเห็น "ของช่วงยาว k", "substring of length k", "ทุก window ขนาด k"

def fixed_window(arr, k):
            window = sum(arr[:k])          # สร้างหน้าต่างแรก
            best = window
            for right in range(k, len(arr)):
                window += arr[right]       # ตัวใหม่เข้า
                window -= arr[right - k]   # ตัวเก่าออก
                best = max(best, window)
            return best

แบบที่ 2 — Variable-size (ขนาดยืดหยุ่น)

ไม่มีความยาวตายตัว: ขยายขวา (expand) รับของเข้าเรื่อย ๆ พอ window invalid ค่อยหดซ้าย (shrink) จนถูกต้องแล้วบันทึกคำตอบ ใช้เมื่อเห็น "ยาวที่สุด / สั้นที่สุด ที่ยัง…", "at most k", "ไม่มีตัวซ้ำ"

def variable_window(arr):
            left = 0
            state = 0                      # ผลรวม / จำนวน / อะไรก็ตามที่ track
            best = 0
            for right in range(len(arr)):
                # 1) Expand: รับ arr[right] เข้าหน้าต่าง
                state += arr[right]

                # 2) Shrink: หดซ้ายจนกว่าหน้าต่างจะถูกต้อง
                while is_invalid(state):   # <- แทนที่ด้วยเงื่อนไขของโจทย์
                    state -= arr[left]
                    left += 1

                # 3) Update: ตรงนี้ [left..right] valid แล้ว
                best = max(best, right - left + 1)
            return best

สัญญาณในโจทย์ — รู้ได้ยังไงว่าต้องใช้ sliding window

ต้องมีสองอย่างพร้อมกัน: (1) คำตอบเป็นช่วงต่อเนื่อง (contiguous — ติดกัน ไม่กระโดดข้ามแบบ subsequence) และ (2) ต้องการค่าดีที่สุดหรือนับภายใต้เงื่อนไข (ยาวสุด / สั้นสุด / ผลรวมมากสุด / ไม่เกิน k ตัว)

ลองไล่ variable window ของจริง

ตัวอย่างคลาสสิก: หา substring ยาวสุดที่ไม่มีตัวซ้ำ (LC3) — invariant คือ "ห้ามมีตัวซ้ำใน window" พอตัวซ้ำเข้าทางขวา ต้องหดซ้ายจนตัวเก่าหลุดออก

s = "abcabcbb"
seen = set()
left = 0
best = 0

for right, ch in enumerate(s):
    while ch in seen:                      # ซ้ำแล้ว → หดซ้าย
        seen.remove(s[left])
        left += 1
    seen.add(ch)                           # รับตัวใหม่เข้า
    best = max(best, right - left + 1)
    print(f"right={right} ch={ch!r} window={s[left:right+1]!r} best={best}")

print("คำตอบ:", best)

right=0 ch='a' window='a' best=1
right=1 ch='b' window='ab' best=2
right=2 ch='c' window='abc' best=3
right=3 ch='a' window='bca' best=3
right=4 ch='b' window='cab' best=3
right=5 ch='c' window='abc' best=3
right=6 ch='b' window='cb' best=3
right=7 ch='b' window='b' best=3
คำตอบ: 3

ตอน right=3 ตัว 'a' ซ้ำ → while เอา 'a' ตัวแรกออก (left ไปที่ 1) window เหลือ "bca" ยาว 3 เท่าเดิม จากนั้นทุกครั้งที่ซ้ำ left ก็ไล่ตาม ความยาวดีสุดค้างที่ 3 ("abc")

Window state — อะไรที่ต้องถือไว้ในมือ

Window ไม่ใช่แค่ left กับ right — ต้องมี state ที่อัปเดตได้เร็วตอนของเข้า/ออก เลือกแบบที่ง่ายสุดที่บอกได้ว่า window ยัง valid ไหมใน O(1)

• ตัวเลขเดียว: ผลรวม, จำนวน 0, จำนวนสระ — ใช้กับ fixed window หรือเงื่อนไขตัวเลข
• set: จำว่ามีตัวไหนอยู่ใน window — ใช้กับ "ห้ามซ้ำ"
• freq map / Counter: นับความถี่ต่อตัวหรือต่อค่า — ใช้กับ "at most k distinct", anagram, ครอบคลุมตัวอักษรของ t
• deque: เก็บตัวแข่ง max/min ใน window — ใช้ตอนถามค่ามากสุด/น้อยสุดในทุก window ยาว k (นอก LC75 หมวดนี้ แต่เจอบ่อยตอนสัมภาษณ์)

ต่างจาก Two Pointers ตรงไหน

พูดอย่างสั้น: sliding window คือ two pointers แบบ same-direction ที่ถือ "ของทั้งช่วง" เป็น state ไว้ด้วย ถ้าโจทย์พูดถึง contiguous / subarray / substring + optimize → นึก window ก่อน

กับดักที่เจอบ่อย

• ความยาว window ผิด: ช่วง inclusive [left..right] ยาว = right - left + 1 ไม่ใช่ right - left
• เริ่ม best = 0 ทั้งที่คำตอบอาจติดลบ — initialize ด้วยหน้าต่างแรก หรือ float("-inf")
• fixed window ลืมสร้างหน้าต่างแรกก่อน loop หรือลบตัวออกผิดตำแหน่ง (ต้อง right - k ไม่ใช่ left)
• variable window อัปเดต best ตอนยัง invalid — ต้อง shrink ให้จบก่อน
• เลขติดลบ + เงื่อนไขผลรวม: อย่าสมมติว่าขยายแล้วผลรวมต้องโต ถ้าเป็น max subarray ทั่วไปให้ไป Kadane
• left ถอยหลังได้ พัง amortized O(n) ทันที — left เดินหน้าอย่างเดียว

สี่ข้อในหมวดนี้ เรียงยังไง

สองข้อแรกซ้อม fixed ให้มือขึ้น สองข้อหลังเป็น variable แบบ "at most k ตัวที่ผิดกติกา" — ข้อ 17 คือข้อ 16 ที่ k ล็อกเป็น 1 ถ้าเข้าใจข้อ 16 แล้ว ข้อ 17 จะรู้เรื่องทันที