Tìm chuỗi con độ dài K không có ký tự lặp lại trong Python

Giả sử chúng ta có một chuỗi S, cần tìm số lượng chuỗi con độ dài K mà không có ký tự nào bị lặp lại. Ví dụ, nếu S = "heyfriendshowareyou" và K = 5, thì kết quả sẽ là 15, các chuỗi con là [heyfr, eyfri, yfrie, frien, riend, iends, endsh, ndsho, dshow, showa, howar, oware, warey, areyo, reyou].

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

• Tạo một map rỗng m, left := 0, right := -1, ans := 0
• Khi right < độ dài chuỗi - 1:
  • Nếu right - left + 1 = K, thì tăng ans lên 1, giảm m[str[left]] đi 1, tăng left lên 1, tiếp tục vòng lặp tiếp theo
  • Nếu str[right + 1] không có trong m, thì đặt m[str[right + 1]] := 1, tăng right lên 1
  • Ngược lại nếu m[str[right + 1]] bằng 0, thì tăng m[str[right + 1]] lên 1, tăng right lên 1
  • Ngược lại, giảm m[str[left]] đi 1, left := left + 1
• Nếu right - left + 1 = K, thì tăng ans lên 1
• Trả về ans

Ví dụ

Xem triển khai sau để hiểu rõ hơn:

class Solution(object):
    def numKLenSubstrNoRepeats(self, S, K):
        m = {}
        left = 0
        right = -1
        ans = 0
        while right < len(S) - 1:
            if right - left + 1 == K:
                ans += 1
                m[S[left]] -= 1
                left += 1
                continue
            if S[right + 1] not in m:
                m[S[right + 1]] = 1
                right += 1
            elif not m[S[right + 1]]:
                m[S[right + 1]] += 1
                right += 1
            else:
                m[S[left]] -= 1
                left += 1
        if right - left + 1 == K:
            ans += 1
        return ans

ob1 = Solution()
print(ob1.numKLenSubstrNoRepeats("heyfriendshowareyou", 5))

Đầu vào

"heyfriendshowareyou" 5

Kết quả

15