Tìm chuỗi con dài nhất có k ký tự duy nhất trong Python

Cho chuỗi s, tìm chuỗi con dài nhất chứa đúng k ký tự duy nhất. Nếu có nhiều chuỗi con cùng độ dài lớn nhất, trả về bất kỳ chuỗi nào.

Ví dụ: s = "ppqprqtqtqt", k = 3 → kết quả "rqtqtqt" (độ dài 7).

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

• Duy trì cửa sổ [start, end] và mảng đếm tần suất 26 ký tự.
• Mở rộng end, cập nhật đếm.
• Nếu số ký tự duy nhất > k: thu hẹp start cho đến khi ≤ k.
• Cập nhật chuỗi con dài nhất khi số ký tự duy nhất == k.

Ví dụ

N = 26

def is_ok(count, k):
    val = 0
    for i in range(N):
        if count[i] > 0:
            val += 1
    return k >= val

def k_unique_chars(s, k):
    unique = 0
    size = len(s)
    count = [0] * N
    for i in range(size):
        if count[ord(s[i]) - ord('a')] == 0:
            unique += 1
        count[ord(s[i]) - ord('a')] += 1
    if unique < k:
        return "Not sufficient characters"
    start = 0
    end = 0
    window_length = 1
    window_start = 0
    count = [0] * N
    count[ord(s[0]) - ord('a')] += 1
    for i in range(1, size):
        count[ord(s[i]) - ord('a')] += 1
        end += 1
        while not is_ok(count, k):
            count[ord(s[start]) - ord('a')] -= 1
            start += 1
        if end - start + 1 > window_length:
            window_length = end - start + 1
            window_start = start
    return s[window_start:window_start + window_length]

s = "ppqprqtqtqt"
k = 3
print(k_unique_chars(s, k))

Đầu vào

"ppqprqtqtqt", 3

Đầu ra

rqtqtqt