โปรแกรมหาความยาวซับสตริงยาวที่สุดที่มีตัวอักษรไม่เกิน 2 ชนิดใน Python

สมมติว่าเรามีสตริง s หาความยาวของซับสตริงยาวที่สุดที่มีตัวอักษรไม่เกิน 2 ชนิด

ตัวอย่าง: s = "xyzzy" ผลลัพธ์ 4 (ซับสตริง "yzzy" มีแค่ y และ z)

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

1. start = 0
2. c = Counter() (นับจำนวนตัวอักษรในหน้าต่าง)
3. ans = 0
4. วนลูป end จาก 0 ถึง len(s)-1:
   • c[s[end]] += 1
   • วนลูป while len(c) > 2:
     • c[s[start]] -= 1
     • ถ้า c[s[start]] == 0: del c[s[start]]
     • start += 1
   • ans = max(ans, end - start + 1)
5. คืนค่า ans

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

class Solution:
    def solve(self, s):
        from collections import Counter
        start = 0
        c = Counter()
        ans = 0
        for end in range(len(s)):
            c[s[end]] += 1
            while len(c) > 2:
                c[s[start]] -= 1
                if not c[s[start]]:
                    del c[s[start]]
                start += 1
            ans = max(ans, end - start + 1)
        return ans

ob = Solution()
s = "xyzzy"
print(ob.solve(s))  # Output: 4

อินพุต / เอาต์พุต

Input: s = "xyzzy"

Output: 4