หาย่อยสตริงความยาว K ที่ไม่มีตัวอักษรซ้ำใน Python

สมมติว่าเรามีสตริง S เราต้องหาจำนวนสตริงย่อยที่มีความยาว K โดยที่ไม่มีตัวอักษรซ้ำกัน ดังนั้นถ้า S = "heyfriendshowareyou" และ K = 5 ผลลัพธ์จะเป็น 15 โดยสตริงคือ [heyfr, eyfri, yfrie, frien, riend, iends, endsh, ndsho, dshow, showa, howar, oware, warey, areyo, reyou]

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

• สร้างแมป m ว่าง และ left := 0, right := -1, ans := 0
• while right < ความยาวของสตริง - 1
  • ถ้า right - left + 1 = k แล้ว
    • เพิ่ม ans ขึ้น 1
    • ลด m[str[left]] ลง 1
    • เพิ่ม left ขึ้น 1
    • continue ไปรอบถัดไป
  • ถ้า str[right + 1] ไม่อยู่ใน m แล้ว
    • ตั้ง m[str[right + 1]] := 1
    • เพิ่ม right ขึ้น 1
  • ถ้า m[str[right + 1]] เป็น 0 แล้ว
    • เพิ่ม m[str[right + 1]] ขึ้น 1
    • เพิ่ม right ขึ้น 1
  • มิฉะนั้น
    • ลด m[str[left]] ลง 1
    • left := left + 1
• ถ้า right - left + 1 = k แล้ว เพิ่ม ans ขึ้น 1
• คืนค่า ans

ตัวอย่าง

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

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

อินพุต

"heyfriendshowareyou" 5

ผลลัพธ์

15