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

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