LeetCode #3 Longest Substring Without Repeating Characters: หน้าต่างเลื่อน

โจทย์ให้สตริง s หาความยาวของสับสตริงต่อเนื่องที่ยาวที่สุดโดยไม่มีตัวอักษรซ้ำ ค่าว่างตอบ 0

วิธีที่ 1: ลองทุกจุดเริ่ม

เลือกซ้ายทุกตำแหน่ง ขยายขวาจนกว่าจะเจอตัวซ้ำในช่วง เวลา O(n²) พื้นที่ O(min(n, Σ)) ใช้เป็น oracle กับอินพุตสั้น

วิธีที่ 2: หน้าต่างเลื่อนกับเซต

เก็บตัวในหน้าต่างด้วย set ขยับขวาทีละตัว ถ้าซ้ำให้เอาตัวซ้ายออกจนไม่ซ้ำ แล้วอัปเดตคำตอบ เวลา O(n) เพราะแต่ละดัชนีเข้า/ออกเซตได้จำกัดครั้ง พื้นที่ O(min(n, Σ))

วิธีที่ 3: จำดัชนีล่าสุด (แนะนำหลัก)

เก็บแผนที่ตัวอักษร → ตำแหน่งล่าสุดที่เห็น เมื่อเจอตัวที่เคยอยู่ในหน้าต่าง ให้กระโดดซ้ายไปหลังตำแหน่งนั้นทันที ยัง O(n)/O(Σ) แต่ลดการเอาออกทีละตัว

import unittest


def length_of_longest_substring_bruteforce(s):
    best = 0
    n = len(s)
    for left in range(n):
        seen = set()
        for right in range(left, n):
            if s[right] in seen:
                break
            seen.add(s[right])
            best = max(best, right - left + 1)
    return best


def length_of_longest_substring(s):
    last = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best


class LongestSubstringTests(unittest.TestCase):
    def test_examples(self):
        cases = [
            ("abcabcbb", 3),
            ("bbbbb", 1),
            ("pwwkew", 3),
            ("", 0),
            ("au", 2),
            ("dvdf", 3),
        ]
        for s, expected in cases:
            with self.subTest(s=s):
                self.assertEqual(length_of_longest_substring(s), expected)
                self.assertEqual(length_of_longest_substring_bruteforce(s), expected)

    def test_unicode_and_space(self):
        self.assertEqual(length_of_longest_substring("a b a"), 3)


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

เลือกตามสถานการณ์

สถานการณ์	วิธี
อธิบายนิยาม / สร้าง oracle	brute force
สอน invariant ของหน้าต่าง	เซตขยาย-หด
ค่าเริ่มต้นในข้อสอบ/โปรดักชันสแกนครั้งเดียว	ดัชนีล่าสุด
ชุดอักขระเล็กมากและอยากแคชอาร์เรย์	แทน map ด้วยอาร์เรย์ขนาด Σ

Recap

• หน้าต่าง [left, right] ต้องไม่มีตัวซ้ำเสมอ
• กระโดดซ้ายด้วยดัชนีล่าสุดเมื่อเจอซ้ำในหน้าต่าง
• ทดสอบสตริงว่าง ตัวเดียว และเคส dvdf
• ใช้ brute force เทียบผลบนสตริงสั้นสุ่มก่อนเชื่อ O(n)