Chương trình cân bằng chuỗi hướng so mỗi hướng xuất hiện n/4 lần Python

Cho chuỗi s chứa 4 ký tự 'N','S','W','E'. Tìm độ dài chuỗi con ngắn nhất cần thay thế để mỗi hướng xuất hiện đúng n/4 lần (n = len(s)).

Ví dụ: s="NNSWWESN" → 1 (thay 'N' cuối thành 'E').

Giải thuật (Cửa sổ trượt)

1. Tính quarter = n // 4, đếm tần suất từng ký tự
2. Xác định target: các ký tự thừa (> quarter) cần giảm bao nhiêu
3. Dùng cửa sổ trượt [left, right] tìm đoạn ngắn nhất chứa đủ ký tự thừa
4. Mở rộng right, thu hẹp left khi điều kiện thỏa mãn

Ví dụ triển khai

from collections import Counter

def solve(s):
    n = len(s)
    if not n:
        return 0
    quarter = n // 4
    count = Counter(s)
    target = {}
    for d, cnt in count.items():
        if cnt > quarter:
            target[d] = quarter - cnt  # giá trị âm = số lượng thừa
    if not target:
        return 0
    left, min_len = 0, float("inf")
    for right, d in enumerate(s):
        if d in target:
            target[d] += 1
        while min(target.values()) >= 0:
            min_len = min(min_len, right - left + 1)
            if s[left] in target:
                target[s[left]] -= 1
            left += 1
    return min_len

print(solve("NNSWWESN"))

Đầu vào

"NNSWWESN"

Đầu ra

1