পাইথনে দেওয়া সাবস্ট্রিং সম্বলিত ন্যূনতম সাবস্ট্রিং আকার বের করার প্রোগ্রাম

ধরুন s এবং t দুটি স্ট্রিং। s-এর ন্যূনতম সাবস্ট্রিংয়ের আকার বের করতে হবে যেটি t-এর সব ক্যারেক্টার ধারণ করে। যদি এমন সাবস্ট্রিং না থাকে তবে -1 রিটার্ন করুন।

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

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

counter := b-এ প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি
start := 0
min_subs := inf
rem := b-এ ভিন্ন ক্যারেক্টারের সংখ্যা
end = 0 থেকে a-এর আকার-১ পর্যন্ত লুপ:
- current := a[end]
- যদি current counter-এ থাকে:
  - counter[current] := counter[current] - 1
  - যদি counter[current] == 0 হয়: rem := rem - 1
- while rem == 0:
  - prev_char := a[start]
  - যদি prev_char counter-এ থাকে:
    - counter[prev_char] := counter[prev_char] + 1
    - যদি counter[prev_char] > 0 হয়: rem := rem + 1
  - min_subs := min(min_subs, end - start + 1)
  - start := start + 1
min_subs != inf হলে min_subs রিটার্ন করুন, অন্যথায় -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"