পাইথনে প্রদত্ত সাবস্ট্রিং ধারণ করে ন্যূনতম স্ট্রিং আকার খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের দুটি স্ট্রিং s এবং t আছে, আমাদের s-এর মধ্যে একটি ন্যূনতম সাবস্ট্রিংয়ের আকার খুঁজে বের করতে হবে যাতে t-এর সমস্ত অক্ষর রয়েছে। যদি এমন কোন সাবস্ট্রিং না থাকে তাহলে -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুটটি s ="thegrumpywizardmakes" t ="wake" এর মত হয়, তাহলে আউটপুট হবে 10, কারণ "wake" ধারণ করা সবচেয়ে ছোট সাবস্ট্রিং হল "wizardmake" (10 এর দৈর্ঘ্য)।

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

counter :=b
এ প্রতিটি অক্ষরের ফ্রিকোয়েন্সি
শুরু :=0
min_subs :=inf
rem :=b
এ স্বতন্ত্র অক্ষরের গণনা
পরিসীমা 0 থেকে a এর আকারের জন্য, করুন
- বর্তমান :=a[শেষ]
- যদি কারেন্ট কাউন্টারে থাকে, তাহলে
  - কাউন্টার[কারেন্ট] :=কাউন্টার[কারেন্ট] - 1
  - যদি কাউন্টার[কারেন্ট] 0 এর মত হয়, তাহলে
    - rem :=rem - 1
- যখন rem 0 এর মতো, কর
  - prev_char :=a[শুরু]
  - যদি prev_char কাউন্টারে থাকে, তাহলে
    - counter[prev_char] :=counter[prev_char] + 1
    - যদি counter[prev_char]> 0 হয়, তাহলে
      - rem :=rem + 1
  - min_subs :=সর্বনিম্ন min_subs এবং (শেষ - শুরু + 1)
  - start :=start + 1
min_subs ফেরত দিন যখন min_subs inf না হয় অন্যথায় -1

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

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

class Solution:
   def solve(self, a, b):
      counter = {}
      for char in b:
         counter[char] = counter.get(char, 0) + 1
      start = 0
      min_subs = float("inf")
      rem = len(counter)
      for end in range(len(a)):
         current = a[end]
         if current in counter:
            counter[current] -= 1
            if counter[current] == 0:
               rem -= 1
         while rem == 0:
            prev_char = a[start]
            if prev_char in counter:
               counter[prev_char] += 1
               if counter[prev_char] > 0:
                  rem += 1
               min_subs = min(min_subs, end - start + 1)
               start += 1
      return min_subs if min_subs != float("inf") else -1
ob = Solution()
s = "thegrumpywizardmakes"
t = "wake"
print(ob.solve(s, t))

ইনপুট

"thegrumpywizardmakes", "wake"