Chương trình đếm chuỗi con độ dài K xuất hiện nhiều hơn 1 lần trong Python

Cho chuỗi và số . Đếm số chuỗi con độ dài xuất hiện > 1 lần trong .

Ví dụ: , → 2 (chuỗi "xx" và "yy").

Giải thuật (Sliding Window + Counter)

1. Tạo danh sách chứa tất cả chuỗi con độ dài .
2. Dùng đếm tần suất.
3. Đếm số phần tử có tần suất > 1.

Ví dụ minh họa

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

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

Đầu vào

"xxxyyy", 2

Đầu ra

2