โปรแกรมนับ Substring ความยาว K ที่เกิดขึ้นมากกว่า 1 ครั้งใน Python

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

ตัวอย่าง: s = "xxxyyy", k = 2 ผลลัพธ์ 2 (คือ "xx" และ "yy")

ขั้นตอนการแก้ปัญหา (Sliding Window + Counter)

1. สร้างรายการ seen เก็บ substring ทุกตัวความยาว k
2. นับความถี่ด้วย Counter
3. นับจำนวนค่าที่ frequency > 1

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

from collections import Counter

class Solution:
    def solve(self, s, k):
        seen = []
        for i in range(len(s) - k + 1):
            t = s[i : i + k]
            seen.append(t)
        freq = Counter(seen)
        return sum(1 for x in freq.values() if x > 1)

ob = Solution()
print(ob.solve("xxxyyy", 2))  # Output: 2

อินพุต

"xxxyyy", 2

เอาต์พุต

2