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

मान लीजिए हमारे पास एक स्ट्रिंग है। हमें बिना वर्णों को दोहराए सबसे लंबा सबस्ट्रिंग ढूंढना है। इसलिए यदि स्ट्रिंग "ABCABCBB" जैसी है, तो परिणाम 3 होगा, क्योंकि लंबाई 3 का एक सबस्ट्रिंग है जो दोहरा रहा है। वह है "ABC"।

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

• i := 0, j := 0 सेट करें, जानकारी स्टोर करने के लिए एक मैप सेट करें
• ans := 0
• जब तक j < स्ट्रिंग s की लंबाई
  • यदि s[j] मैप में मौजूद नहीं है, या i > map[s[j]], तो
    • ans := max(ans, j - i + 1)
    • map[s[j]] := j
  • अन्यथा
    • i := map[s[j]] + 1
    • ans := max(ans, j - i + 1)
    • j को 1 से घटाएं
  • j को 1 से बढ़ाएं
• ans लौटाएं

उदाहरण (पायथन)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        i = 0
        j = 0
        d = {}
        ans = 0
        while j < len(s):
            if s[j] not in d or i > d[s[j]]:
                ans = max(ans, (j-i+1))
                d[s[j]] = j
            else:
                i = d[s[j]] + 1
                ans = max(ans, (j-i+1))
                j -= 1
            # print(ans)
            j += 1
        return ans

ob1 = Solution()
print(ob1.lengthOfLongestSubstring("ABCABCBB"))

इनपुट

"ABCABCBB"

आउटपुट

3