หาสตริงย่อยที่ยาวที่สุดที่มีตัวอักษรไม่ซ้ำ k ตัวใน Python

สมมติว่าเรามีสตริง ต้องการหาสตริงย่อยที่ยาวที่สุดที่มีตัวอักษรไม่ซ้ำกันพอดี k ตัว หากมีหลายสตริงยาวเท่ากัน คืนค่าตัวใดตัวหนึ่ง

เช่น s = "ppqprqtqtqt", k = 3 ผลลัพธ์คือ rqtqtqt (ความยาว 7)

ขั้นตอนการแก้ปัญหา (Sliding Window)

นับตัวอักษรที่ไม่ซ้ำในสตริงทั้งหมด ถ้าน้อยกว่า k คืนค่าไม่พบ
ใช้ Sliding Window พร้อมอาร์เรย์นับความถี่ขนาด 26
ขยายหน้าต่างด้านขวา จนกว่าจะมีตัวอักษรไม่ซ้ำเกิน k
เมื่อเกิน k ให้ยุบหน้าต่างด้านซ้ายจนกว่าจะถูกต้อง
บันทึกหน้าต่างที่ยาวที่สุด

ตัวอย่างโค้ด Python

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))

อินพุต

"ppqprqtqtqt", 3

เอาต์พุต

rqtqtqt