Chương trình tìm độ dài chuỗi con nhỏ nhất chứa tất cả ký tự của chuỗi khác trong Python

Cho 2 chuỗi s, t. Tìm độ dài chuỗi con nhỏ nhất của s chứa tất cả ký tự của t (theo tần suất). Không tồn tại → -1.

Ví dụ: s="thegrumpywizardmakes", t="wake" → 10 (chuỗi con "wizardmake").

Giải thuật (Cửa sổ trượt + HashMap đếm)

1. Đếm tần suất ký tự trong t → counter. rem = số ký tự distinct còn thiếu.
2. Mở rộng cửa sổ phải end: giảm counter, nếu về 0 → rem--.
3. Khi rem == 0 (đủ ký tự): thu hẹp cửa sổ trái start để tối thiểu độ dài, cập nhật min_subs.

Ví dụ minh họa

class Solution:
    def solve(self, a, b):
        counter = {}
        for ch in b:
            counter[ch] = counter.get(ch, 0) + 1
        start = 0
        min_subs = 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_subs = min(min_subs, 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_subs if min_subs != float('inf') else -1

ob = Solution()
s = "thegrumpywizardmakes"
t = "wake"
print(ob.solve(s, t))  # Output: 10 (sửa từ 2 trong gốc)

Đầu vào / Đầu ra

Input: "thegrumpywizardmakes", "wake"

Output: 10