পাইথনে লองেস্ট সাবস্ট্রিং উইথআউট রিপিটিং ক্যারেক্টারস

ধরা যাক একটি স্ট্রিং দেওয়া আছে। повтор হ্রাস না করে সবচেয়ে বড় সাবস্ট্রিং খুঁজে বের করতে হবে। যদি স্ট্রিং হয় "ABCABCBB", তবে ফলাফল হবে 3, কারণ "ABC" একটি ৩ দৈর্ঘ্যের রিপিটিং সাবস্ট্রিং।

সমাধানের ধাপসমূহ:

• i := 0, j := 0 সেট করুন, তথ্য সংরক্ষণের জন্য একটি ম্যাপ তৈরি করুন
• ans := 0
• while j < length of string s
  • if s[j] ম্যাপে নেই, অথবা i > map[s[j]], তবে
    • ans := max(ans, j - i + 1)
    • map[s[j]] := j
  • otherwise
    • i := map[s[j]] + 1
    • ans := max(ans, j - i + 1)
    • j ১ কমানো
  • j ১ বাড়ান
• 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
            j += 1
        return ans

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

ইনপুট

"ABCABCBB"

আউটপুট

3