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

สมมติว่ามีสตริง s ที่ตัวอักษรเรียงแล้ว และตัวเลข k ต้องการหาความยาว substring ยาวที่สุดที่ทุกตัวอักษรเกิดขึ้น ≥ k ครั้ง

ตัวอย่าง: s = "aabccddeeffghij", k = 2 ผลลัพธ์ 8 substring คือ "ccddeeff"

ขั้นตอนการแก้ปัญหา

1. ฟังก์ชัน rc(lst) แบบ recursive:
   • นับความถี่ c ของทุกตัวอักษร
   • acc = [], ans = 0, valid = True
   • วนแต่ละ x ใน lst:
     • ถ้า c[x] < k: valid = False, ans = max(ans, rc(acc)), acc = []
     • มิฉะนั้น: เพิ่ม x เข้า acc
   • ถ้า valid: คืน len(acc)
   • มิฉะนั้น: ans = max(ans, rc(acc)), คืน ans
2. คืน rc(list(s))

ตัวอย่างโค้ด

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