สมมติว่าเรามีสตริง S เราต้องหาจำนวนสตริงย่อยที่มีความยาว K โดยที่ไม่มีอักขระซ้ำ ดังนั้นถ้า S =“heyfriendshowareyou” และ K คือ 5 ผลลัพธ์จะเป็น 15 เนื่องจากสตริงคือ [heyfr, eyfri, yfrie, frien, riend, iends, endsh, ndsho, dshow, showa, howar, oware, warey, areyo , คุณ]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างแผนที่ว่างหนึ่งแผนที่ m และซ้าย :=0 และขวา :=-1 และ ans :=0
- ในขณะที่ขวา <ความยาวของสตริง – 1
- ถ้าขวา – ซ้าย + 1 =k แล้ว
- เพิ่ม ans ขึ้น 1
- ลด m[str[left]] ลง 1
- เพิ่มขึ้นทางซ้าย 1
- ไปต่อตอนต่อไป
- ถ้า str[right + 1] ไม่อยู่ใน m แล้ว
- set m[str[right + 1]] :=1
- เพิ่มสิทธิ์ 1
- ถ้า m[str[right + 1]] เป็น 0 แล้ว
- เพิ่ม m[str[right + 1]] ขึ้น 1
- เพิ่มสิทธิ์ 1
- อย่างอื่น
- ลด m[str[left]] ลง 1
- ซ้าย :=ซ้าย + 1
- ถ้าขวา – ซ้าย + 1 =k แล้ว
- ถ้า ขวา – ซ้าย + 1 =k ให้เพิ่ม ans ขึ้น 1
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
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
ผลลัพธ์
"AIIOC"
