Chương trình tìm độ dài của chuỗi con dài nhất với số ký tự ít nhất là k trong Python

Giả sử chúng ta có một chuỗi s trong đó mỗi ký tự được sắp xếp và chúng ta cũng có số k, chúng ta phải tìm độ dài của chuỗi con dài nhất sao cho mọi ký tự xuất hiện ít nhất k lần.

Vì vậy, nếu đầu vào là s =​​"aabccddeeffghij" k =2, thì đầu ra sẽ là 8, vì chuỗi con dài nhất ở đây là "ccddeeff" ở đây mỗi ký tự xuất hiện ít nhất 2 lần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm rc (). Điều này sẽ mất khoảng
• c:=một bản đồ với tất cả các ký tự và sự xuất hiện của chúng
• acc:=một danh sách mới
• ans:=0
• hợp lệ:=True
• đối với mỗi x trong lst, thực hiện
  • nếu c [x]
  • hợp lệ:=Sai
  • ans:=tối đa ans và rc (acc)
  • acc:=một danh sách mới
• nếu không,
  • chèn x vào cuối tài khoản

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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