โปรแกรมหาขนาด substring น้อยที่สุดที่มีตัวอักษรครบใน Python

ได้รับสตริง s และ t หา ความยาว substring สั้นที่สุดของ s ที่มีตัวอักษรครบทุกตัวใน t (ตามจำนวน) ไม่มี → -1

ตัวอย่าง

Input: s = "thegrumpywizardmakes", t = "wake"

Output: 10 (substring "wizardmake")

หมายเหตุ: ตัวอย่าง Output ในโจทย์ต้นฉบับเขียน 2 ซึ่งผิด ควรเป็น 10

แนวทางแก้ปัญหา

ใช้ Sliding Window + Character Count:

1. นับความถี่ตัวอักษรใน t → counter
2. rem = จำนวนตัวอักษรที่ยังไม่ครบ (distinct chars)
3. ขยาย window ด้านขวา (end) จน rem == 0
4. หด window ด้านซ้าย (start) ขณะ rem == 0 อัปเดตคำตอบ

การใช้งาน (Python)

class Solution:
    def solve(self, a, b):
        from collections import Counter
        counter = Counter(b)
        start = 0
        min_len = float('inf')
        rem = len(counter)
        
        for end, ch in enumerate(a):
            if ch in counter:
                counter[ch] -= 1
                if counter[ch] == 0:
                    rem -= 1
            
            while rem == 0:
                min_len = min(min_len, end - start + 1)
                left_ch = a[start]
                if left_ch in counter:
                    counter[left_ch] += 1
                    if counter[left_ch] > 0:
                        rem += 1
                start += 1
        
        return min_len if min_len != float('inf') else -1

# ทดสอบ
ob = Solution()
print(ob.solve("thegrumpywizardmakes", "wake"))  # Output: 10

ความซับซ้อน

• Time Complexity: O(|s| + |t|)
• Space Complexity: O(|Alphabet|)