Chương trình tìm độ dài dãy con anagram dài nhất trong Python

Cho hai chuỗi chữ thường S và T, tìm độ dài dãy con anagram dài nhất (các ký tự xuất hiện trong cả hai chuỗi, không cần liên tiếp).

Ví dụ: S = "helloworld", T = "hellorld" → kết quả 8.

Giải thuật (Đếm tần suất ký tự)

1. Đếm tần suất ký tự trong S → dict c.
2. Đếm tần suất ký tự trong T → dict d.
3. Khởi tạo res = 0.
4. Duyệt từng ký tự ch trong c:
   • Nếu có trong d: res += min(c[ch], d[ch]).
5. Trả về res.

Ví dụ minh họa

class Solution:
    def solve(self, a, b):
        c, d = {}, {}
        for ch in a:
            c[ch] = c.get(ch, 0) + 1
        for ch in b:
            d[ch] = d.get(ch, 0) + 1
        res = 0
        for ch in c:
            if d.get(ch, 0) > 0:
                res += min(c[ch], d[ch])
        return res

ob = Solution()
S = "helloworld"
T = "hellorld"
print(ob.solve(S, T))  # Output: 8

Đầu vào

S = "helloworld", T = "hellorld"

Đầu ra

8