ধরুন আমাদের একটি স্ট্রিং S আছে, আমাদের K দৈর্ঘ্যের সাবস্ট্রিংগুলির সংখ্যা খুঁজে বের করতে হবে যেখানে কোনও অক্ষর পুনরাবৃত্তি হয় না। সুতরাং যদি S =“heyfriendshowareyou” এবং K হয় 5, তাহলে আউটপুট হবে 15, যেমন স্ট্রিংগুলি হল [heyfr, eyfri, yfrie, frien, riend, iends, endsh, ndsho, dshow, showa, Howar, oware, warey, areyo , reyou]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি খালি মানচিত্র m, এবং বামে তৈরি করুন :=0 এবং ডানে :=-1 এবং উত্তর :=0
- যখন ডানে <স্ট্রিংয়ের দৈর্ঘ্য – 1
- যদি ডান - বাম + 1 =k, তারপর
- উত্তর 1 দ্বারা বৃদ্ধি করুন
- m[str[left]] 1 কমিয়ে দিন
- বামে 1 বাড়ান
- পরবর্তী পুনরাবৃত্তি চালিয়ে যান
- যদি str[right + 1] m এ না থাকে, তাহলে
- সেট 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, তাহলে উত্তর 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"
