หา Substring สั้นที่สุดที่มีตัวอักษรครบทุกตัวของสตริงอีกตัวใน Python

Minimum Window Substring

กำหนดสตริง s1 (หลัก) และ s2 (รูปแบบ) หา Substring สั้นที่สุดใน s1 ที่มีตัวอักษรครบทุกตัวของ s2 (ตามจำนวนครั้งที่ปรากฏ)

ตัวอย่าง: s1="I am a student", s2="mdn" → "m a studen"

อัลกอริทึม Sliding Window (O(N))

1. นับความถี่ตัวอักษรใน s2 → hash_pat
2. ขยายหน้าต่างด้านขวา (j) จนครบทุกตัวอักษรที่ต้องการ
3. เมื่อครบแล้ว ยุบหน้าต่างด้านซ้าย (start) มากที่สุดเท่าที่จะทำได้โดยยังคงครบเงื่อนไข
4. อัปเดตความยาวน้อยสุดและตำแหน่งเริ่มต้น

โค้ดตัวอย่าง Python

def min_window(main_str, pattern):
    if len(main_str) < len(pattern):
        return None
    N = 256
    hash_pat = [0] * N
    hash_str = [0] * N
    for ch in pattern:
        hash_pat[ord(ch)] += 1
    start = start_idx = 0
    min_len = float('inf')
    count = 0
    for j, ch in enumerate(main_str):
        hash_str[ord(ch)] += 1
        if hash_pat[ord(ch)] != 0 and hash_str[ord(ch)] <= hash_pat[ord(ch)]:
            count += 1
        if count == len(pattern):
            while hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])] or hash_pat[ord(main_str[start])] == 0:
                if hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]:
                    hash_str[ord(main_str[start])] -= 1
                start += 1
            window_len = j - start + 1
            if min_len > window_len:
                min_len = window_len
                start_idx = start
    if start_idx == -1:
        return None
    return main_str[start_idx:start_idx+min_len]

print(min_window("I am a student", "mdn"))  # "m a studen"