Giả sử chúng ta có một số k và một chuỗi s khác, chúng ta phải tìm kích thước của chuỗi con dài nhất chứa nhiều nhất k ký tự riêng biệt.
Vì vậy, nếu đầu vào là k =3 s ="kolkata", thì đầu ra sẽ là 4, vì có hai chuỗi con dài nhất với 3 ký tự riêng biệt là "kolk" và "kata", có độ dài 4.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ans:=0, left:=0
-
table:=a new map
-
đối với bên phải nằm trong phạm vi từ 0 đến kích thước của s-1, làm
-
table [s [right]]:=1 + (s [right] nếu tồn tại, nếu không thì 0)
-
nếu kích thước của bảng <=k, thì
-
ans:=tối đa ans và (phải - trái + 1)
-
-
nếu không,
-
trong khi kích thước của bảng> k, do
-
left_char:=s [left]
-
nếu bảng [left_char] giống 1, thì
-
xóa phần tử thứ left_char khỏi bảng
-
-
nếu không,
-
table [left_char]:=table [left_char] - 1
-
-
left:=left + 1
-
-
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution:
def solve(self, k, s):
ans = 0
left = 0
table = {}
for right in range(0, len(s)):
table[s[right]] = table.get(s[right], 0) + 1
if len(table) <= k:
ans = max(ans, right − left + 1)
else:
while len(table) > k:
left_char = s[left]
if table[left_char] == 1:
table.pop(left_char)
else:
table[left_char] −= 1
left += 1
return ans
ob = Solution()
k = 3
s = "kolkata"
print(ob.solve(k, s)) Đầu vào
"anewcoffeepot"
Đầu ra
4