สมมติว่าเรามีตัวเลข k และสตริง s อื่น เราต้องหาขนาดของสตริงย่อยที่ยาวที่สุดที่มีอักขระต่างกันไม่เกิน k ตัว
ดังนั้น หากอินพุตเป็นเหมือน k =3 s ="โกลกาตา" เอาต์พุตจะเป็น 4 เนื่องจากมีสตริงย่อยที่ยาวที่สุดสองสตริงที่มีอักขระต่างกัน 3 ตัว ซึ่งได้แก่ "kolk" และ "kata" ซึ่งมีความยาว 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ตอบ :=0, ซ้าย :=0
-
table :=แผนที่ใหม่
-
สำหรับด้านขวาอยู่ในช่วง 0 ถึงขนาด s − 1 ทำ
-
table[s[right]] :=1 + (s[right] ถ้ามีอยู่ 0)
-
ถ้าขนาดของตาราง <=k แล้ว
-
ans :=สูงสุดของ ans และ (ขวา - ซ้าย + 1)
-
-
มิฉะนั้น
-
ในขณะที่ขนาดของตาราง> k ทำ
-
left_char :=s[ซ้าย]
-
ถ้า table[left_char] เหมือนกับ 1 แล้ว
-
ลบองค์ประกอบ left_char−th ออกจากตาราง
-
-
มิฉะนั้น
-
table[left_char] :=table[left_char] − 1
-
-
ซ้าย :=ซ้าย + 1
-
-
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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)) อินพุต
"anewcoffeepot"
ผลลัพธ์
4
