LeetCode #76 Minimum Window Substring: Sliding Window ที่นับ Duplicate ถูก

Minimum Window Substring ให้หาช่วงสั้นที่สุดใน s ที่มีตัวอักษรของ t ครบ รวมจำนวนซ้ำ ถ้า t มี A สองตัว หน้าต่างที่มี A ตัวเดียวไม่ผ่านครับ

วิธี 1: ตรวจทุกจุดเริ่ม

ขยายปลายขวาจากทุกตำแหน่งจน counter ครบ แล้วเก็บช่วงสั้นสุด วิธีนี้อธิบายง่ายแต่แย่สุด O(n² + m) และทำงานซ้ำสูง ใช้เป็น oracle สำหรับ test ขนาดเล็กได้

วิธี 2: Sliding Window (default)

ขยาย right ให้หน้าต่างครบ แล้วเลื่อน left ตัดส่วนเกินออก ตัวแปร required คือจำนวน key ที่ต้องครบ ส่วน formed เพิ่มเมื่อ count ของ key นั้น เท่ากับ เป้าครั้งแรก และลดเมื่อหลุดต่ำกว่าเป้า ทำให้เช็คครบได้ O(1) ต่อก้าว

from __future__ import annotations

import unittest
from collections import Counter, defaultdict


def brute_force(s: str, t: str) -> str:
    if not t:
        return ""
    need = Counter(t)
    best = ""
    for left in range(len(s)):
        seen: Counter[str] = Counter()
        for right in range(left, len(s)):
            seen[s[right]] += 1
            if all(seen[key] >= count for key, count in need.items()):
                candidate = s[left:right + 1]
                if not best or len(candidate) < len(best):
                    best = candidate
                break
    return best


def sliding_window(s: str, t: str) -> str:
    if not s or not t:
        return ""
    need = Counter(t)
    window: defaultdict[str, int] = defaultdict(int)
    required = len(need)
    formed = left = 0
    best_length = len(s) + 1
    best_left = 0

    for right, char in enumerate(s):
        window[char] += 1
        if char in need and window[char] == need[char]:
            formed += 1
        while formed == required:
            if right - left + 1 < best_length:
                best_length, best_left = right - left + 1, left
            outgoing = s[left]
            window[outgoing] -= 1
            if outgoing in need and window[outgoing] < need[outgoing]:
                formed -= 1
            left += 1
    return "" if best_length > len(s) else s[best_left:best_left + best_length]


class MinimumWindowTests(unittest.TestCase):
    def test_both_methods(self):
        cases = [
            ("ADOBECODEBANC", "ABC", "BANC"),
            ("a", "aa", ""),
            ("AAAB", "AAB", "AAB"),
            ("anything", "", ""),
        ]
        for solve in (brute_force, sliding_window):
            for source, target, expected in cases:
                self.assertEqual(solve(source, target), expected)


if __name__ == "__main__":
    unittest.main()

Decision table

เงื่อนไข	Brute force	Sliding window
เวลา	O(n²·k) ในรูปทั่วไป	O(n+m)
พื้นที่	O(k)	O(k)
รองรับ duplicate	ใช่ เมื่อใช้ count	ใช่ ด้วย formed
input streaming	ไม่เหมาะ	ขยายขวาได้ แต่ต้องเก็บช่วงที่ยังเปิด
mutation input	ไม่มี	ไม่มี
เหมาะใช้จริง	เฉพาะ oracle เล็ก	ใช่

Recap

• นับจำนวนซ้ำ ไม่เช็คแค่ set membership
• เพิ่ม formed เฉพาะตอน count แตะเป้า
• หดซ้ายจนหน้าต่างกำลังจะไม่ครบ
• เทสต์ target ว่าง, หาไม่เจอ และตัวซ้ำ