Chương trình tìm độ dài chuỗi con dài nhất với số lần xuất hiện ký tự ít nhất k trong Python

Mô tả bài toán

Cho chuỗi s (các ký tự đã sắp xếp) và số k. Tìm độ dài chuỗi con dài nhất sao cho mọi ký tự trong chuỗi con đó xuất hiện ít nhất k lần.

Ví dụ: s = "aabccddeeffghij", k = 2 → đầu ra 8 (chuỗi con "ccddeeff").

Giải thuật (Đệ quy chia để trị)

1. Định nghĩa hàm rc(lst):
   • Đếm tần suất c của các ký tự trong lst.
   • Duyệt lst, tách thành các đoạn không chứa ký tự có tần suất < k.
   • Đệ quy tính độ dài lớn nhất cho mỗi đoạn.
   • Nếu toàn bộ đoạn hợp lệ (không có ký tự nào < k), trả về độ dài đoạn.
2. Gọi rc(list(s)).

Ví dụ mã Python

from collections import Counter

class Solution:
    def solve(self, s, k):
        def rc(lst):
            c = Counter(lst)
            acc = []
            ans = 0
            valid = True
            for x in lst:
                if c[x] < k:
                    valid = False
                    ans = max(ans, rc(acc))
                    acc = []
                else:
                    acc.append(x)
            if valid:
                return len(acc)
            else:
                ans = max(ans, rc(acc))
                return ans
        return rc(list(s))

ob = Solution()
s = "aabccddeeffghij"
k = 2
print(ob.solve(s, k))

Đầu vào

"aabccddeeffghij", 2

Đầu ra

8