Tìm cửa sổ nhỏ nhất trong chuỗi chứa tất cả ký tự của chuỗi khác trong Python

Cho hai chuỗi s1 và s2, ta cần tìm chuỗi con nhỏ nhất trong s1 chứa tất cả các ký tự của s2.

Ví dụ, với s1 = "I am a student", s2 = "mdn", kết quả là "m a studen".

Thuật toán giải quyết (Sliding Window)

• Khởi tạo mảng tần suất hash_pat cho s2 và hash_str cho cửa sổ.
• Duyệt j qua s1, cập nhật hash_str.
• Khi cửa sổ chứa đủ ký tự (count == len(s2)), thu hẹp cửa sổ từ trái (start) càng nhiều càng tốt.
• Cập nhật độ dài nhỏ nhất và vị trí bắt đầu.
• Trả về chuỗi con tương ứng.

Ví dụ minh họa

N = 256

def get_pattern(main_str, pattern):
    str_len = len(main_str)
    patt_len = len(pattern)
    if str_len < patt_len:
        return None
    hash_pat = [0] * N
    hash_str = [0] * N
    for i in range(patt_len):
        hash_pat[ord(pattern[i])] += 1
    start, start_index, min_len = 0, -1, float('inf')
    count = 0
    for j in range(str_len):
        hash_str[ord(main_str[j])] += 1
        if hash_pat[ord(main_str[j])] != 0 and hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]:
            count += 1
        if count == patt_len:
            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
            len_window = j - start + 1
            if min_len > len_window:
                min_len = len_window
                start_index = start
    if start_index == -1:
        return None
    return main_str[start_index : start_index + min_len]

main_str = "I am a student"
pattern = "mdn"
print(get_pattern(main_str, pattern))  # m a studen

Đầu vào

"I am a student", "mdn"

Đầu ra

m a studen