পাইথনে অক্ষর পুনরাবৃত্তি ছাড়াই দীর্ঘতম সাবস্ট্রিং

ধরুন আমাদের একটি স্ট্রিং আছে। আমাদের অক্ষর পুনরাবৃত্তি না করে দীর্ঘতম সাবস্ট্রিং খুঁজে বের করতে হবে। সুতরাং যদি স্ট্রিংটি "ABCABCBB" এর মত হয়, তাহলে ফলাফল হবে 3, কারণ একটি সাবস্ট্রিং আছে যা পুনরাবৃত্তি হচ্ছে, দৈর্ঘ্য 3। সেটি হল "ABC"।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব

• সেট i :=0, j :=0, তথ্য সংরক্ষণের জন্য একটি মানচিত্র সেট করুন
• উত্তর :=0
• যখন j <স্ট্রিং এর দৈর্ঘ্য s
  • যদি s[j] মানচিত্রে উপস্থিত না থাকে, অথবা i> map[s[j]], তাহলে
    • উত্তর :=max(ans, j – i + 1)
    • মানচিত্র[s[j]] :=j
  • অন্যথায়
    • i :=মানচিত্র[s[j]] + 1
    • উত্তর :=max(ans, j – i + 1)
    • j 1 দ্বারা কমিয়ে দিন
  • j 1 দ্বারা বাড়ান
• উত্তর ফেরত দিন

উদাহরণ (পাইথন)

আরও ভালোভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি

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