โปรแกรมหาความยาวของสตริงย่อยที่มีตัวอักษรที่แตกต่างกันสูงสุด k ตัวใน Python

สมมติว่าเรามีตัวเลข k และสตริง s เราต้องการหาขนาดของสตริงย่อย (substring) ที่ยาวที่สุดซึ่งมีตัวอักษรที่แตกต่างกันไม่เกิน k ตัว

เช่น ถ้าข้อมูลนำเข้าคือ k = 3 s = "kolkata" ผลลัพธ์จะเป็น 4 เนื่องจากมีสตริงย่อยที่ยาวที่สุด 2 ตัวที่มีตัวอักษรแตกต่างกัน 3 ตัว คือ "kolk" และ "kata" ซึ่งมีความยาว 4

ขั้นตอนการแก้ปัญหา

กำหนด ans = 0, left = 0
สร้างตารางแฮช table ว่าง
วนลูป right ตั้งแต่ 0 ถึงขนาดของ s - 1:
- อัปเดตจำนวนของ s[right] ใน table
- ถ้าขนาดของ table <= k ให้ ans := max(ans, right - left + 1)
- มิฉะนั้น (ขนาด > k):
  - วนลูป while ขนาดของ table > k:
    - left_char := s[left]
    - ถ้า table[left_char] == 1 ให้ลบ left_char ออกจาก table
    - มิฉะนั้น ให้ลดค่า table[left_char] ลง 1
    - left := left + 1
คืนค่า ans

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

class Solution:
    def solve(self, k, s):
        ans = 0
        left = 0
        table = {}
        for right in range(0, len(s)):
            table[s[right]] = table.get(s[right], 0) + 1
            if len(table) <= k:
                ans = max(ans, right - left + 1)
            else:
                while len(table) > k:
                    left_char = s[left]
                    if table[left_char] == 1:
                        table.pop(left_char)
                    else:
                        table[left_char] -= 1
                    left += 1
        return ans

ob = Solution()
k = 3
s = "kolkata"
print(ob.solve(k, s))

ข้อมูลนำเข้า

"anewcoffeepot"