पायथन में दोहराए गए वर्णों के साथ के-लंबाई वाले सबस्ट्रिंग खोजें

मान लीजिए कि हमारे पास एक स्ट्रिंग S है, हमें लंबाई K के सबस्ट्रिंग्स की संख्या ज्ञात करनी है जहां कोई वर्ण दोहराया नहीं गया है। तो अगर एस ="हेफ्रेंडशोअरेयू" और के 5 है, तो आउटपुट 15 होगा, क्योंकि स्ट्रिंग्स [हेफ्र, आईफ्री, यफ्री, फ्रेन, रेन्ड, आईंड्स, एंडश, एनडीशो, डीशो, शोआ, होवर, ओवरे, वेरी, अरेयो हैं। , रेयू]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक खाली नक्शा एम बनाएं, और बाएं:=0 और दाएं:=-1 और उत्तर:=0
• जबकि दाएं <स्ट्रिंग की लंबाई - 1
  • यदि दाएँ - बाएँ + 1 =k, तो
    • उत्तरों को 1 से बढ़ाएँ
    • m[str[left]] को 1 से कम करें
    • बाएं 1 से बढ़ाएं
    • अगले पुनरावृत्ति के लिए जारी रखें
  • यदि str[right + 1] m में नहीं है, तो
    • सेट एम[str[दाएं + 1]]:=1
    • दाएं 1 से बढ़ाएं
  • अन्यथा यदि m[str[right + 1]] 0 है, तो
    • m[str[right + 1]] 1 से बढ़ाएं
    • दाएं 1 से बढ़ाएं
  • अन्य
    • m[str[left]] को 1 से कम करें
    • बाएं:=बाएं + 1
• यदि दाएँ - बाएँ + 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"