โปรแกรมค้นหาความยาวของสตริงย่อยที่ยาวที่สุดโดยมีจำนวนอักขระอย่างน้อย k ใน Python

สมมติว่าเรามีสตริงที่จัดเรียงอักขระแต่ละตัวและเรายังมีตัวเลข k เราต้องหาความยาวของสตริงย่อยที่ยาวที่สุดเพื่อให้อักขระทุกตัวเกิดขึ้นอย่างน้อย k ครั้ง

ดังนั้น หากอินพุตเป็น s ="aabccddeeffghij" k =2 เอาต์พุตจะเป็น 8 เนื่องจากสตริงย่อยที่ยาวที่สุดที่นี่คือ "ccddeeff" ที่นี่ทุกอักขระเกิดขึ้นอย่างน้อย 2 ครั้ง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน rc() นี่จะใช้เวลา lst
• c :=แผนที่ที่มีตัวละครทั้งหมดและเหตุการณ์ที่เกิดขึ้น
• acc :=รายการใหม่
• ตอบ :=0
• ถูกต้อง :=จริง
• สำหรับแต่ละ x ใน lst ทำ
  • ถ้า c[x]
  • ถูกต้อง :=เท็จ
  • ans :=สูงสุดของ ans และ rc(acc)
  • acc :=รายการใหม่
• มิฉะนั้น
  • ใส่ x ต่อท้าย acc

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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))

อินพุต

"aabccddeeffghij", 2

ผลลัพธ์

8