Chương trình tìm độ dài xâu con dài nhất có tối đa 2 ký tự phân biệt bằng Python

Cho chuỗi s, tìm độ dài xâu con dài nhất chứa tối đa 2 ký tự khác nhau.

Ví dụ: s = "xyzzy" → 4 (xâu con "yzzy").

Quy trình giải quyết (Sliding Window)

1. Khởi tạo start = 0, Counter c, ans = 0.
2. Với end từ 0 đến len(s)-1:
   • Tăng c[s[end]].
   • Trong khi len(c) > 2:
     • Giảm c[s[start]], nếu về 0 thì xóa khỏi c.
     • Tăng start.
3. Cập nhật ans = max(ans, end - start + 1).
4. Trả về ans.

Ví dụ mã nguồn

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

Đầu vào

s = "xyzzy"

Đầu ra

4