Kỹ thuật cửa sổ trượt

def max_tong_khi_cua_so_co_dinh(arr, k):
    """Tìm tổng lớn nhất của dãy con liên tiếp k phần tử."""
    n = len(arr)
    if n < k:
        return None

    # Tính tổng cửa sổ đầu tiên
    tong = sum(arr[:k])
    max_tong = tong

    # Trượt cửa sổ: bỏ phần tử trái, thêm phần tử phải
    for i in range(k, n):
        tong += arr[i] - arr[i - k]
        max_tong = max(max_tong, tong)

    return max_tong

arr = [2, 1, 5, 1, 3, 2]
print(max_tong_khi_cua_so_co_dinh(arr, 3))   # 9 (dãy [5, 1, 3])
print(max_tong_khi_cua_so_co_dinh(arr, 2))   # 6 (dãy [5, 1] hay [3,2]? → [5,1] cho 6)

def day_con_ngan_nhat_co_tong_du(arr, target):
    """
    Tìm độ dài nhỏ nhất của dãy con liên tiếp có tổng >= target.
    Cửa sổ mở rộng từ phải, thu nhỏ từ trái khi đủ điều kiện.
    """
    left = 0
    tong = 0
    min_len = float('inf')

    for right in range(len(arr)):
        tong += arr[right]
        while tong >= target:
            min_len = min(min_len, right - left + 1)
            tong -= arr[left]
            left += 1

    return min_len if min_len != float('inf') else 0

print(day_con_ngan_nhat_co_tong_du([2, 3, 1, 2, 4, 3], 7))   # 2 ([4,3])
print(day_con_ngan_nhat_co_tong_du([1, 4, 4], 4))              # 1 ([4])
print(day_con_ngan_nhat_co_tong_du([1, 1, 1, 1, 1], 11))       # 0 (không có)

def trung_binh_cua_so(arr, k):
    """Trả về danh sách trung bình liên tiếp của từng cửa sổ k phần tử."""
    n = len(arr)
    if n < k:
        return []

    tong = sum(arr[:k])
    result = [tong / k]

    for i in range(k, n):
        tong += arr[i] - arr[i - k]
        result.append(tong / k)

    return result

arr = [1, 3, 2, 6, -1, 4, 1, 8, 2]
print(trung_binh_cua_so(arr, 5))
# [2.2, 2.8, 2.4, 3.6, 2.8]

def chuoi_con_khong_trung_dai_nhat(s):
    """
    Tìm độ dài chuỗi con liên tiếp không có ký tự lặp.
    Dùng dict để biết ký tự xuất hiện lần cuối ở đâu.
    """
    last_seen = {}    # ký tự → vị trí xuất hiện gần nhất
    left = 0
    max_len = 0

    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # Thu hẹp cửa sổ
        last_seen[ch] = right
        max_len = max(max_len, right - left + 1)

    return max_len

print(chuoi_con_khong_trung_dai_nhat("abcabcbb"))   # 3 ("abc")
print(chuoi_con_khong_trung_dai_nhat("bbbbb"))       # 1 ("b")
print(chuoi_con_khong_trung_dai_nhat("pwwkew"))      # 3 ("wke")

from collections import Counter

def cua_so_nho_nhat_chua_t(s, t):
    """
    Tìm chuỗi con ngắn nhất của s chứa đủ tất cả ký tự của t.
    """
    if not t or not s:
        return ""

    need = Counter(t)      # Số lần cần có của mỗi ký tự
    missing = len(t)       # Số ký tự còn thiếu
    best = ""
    left = 0

    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1    # Thoả mãn thêm 1 ký tự cần
        need[ch] -= 1

        while missing == 0:   # Cửa sổ đang đủ điều kiện → thu nhỏ từ trái
            window = s[left:right + 1]
            if not best or len(window) < len(best):
                best = window
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1

    return best

print(cua_so_nho_nhat_chua_t("ADOBECODEBANC", "ABC"))   # "BANC"
print(cua_so_nho_nhat_chua_t("a", "a"))                  # "a"
print(cua_so_nho_nhat_chua_t("a", "aa"))                 # "" (không đủ)