न्यूनतम स्ट्रिंग आकार खोजने का कार्यक्रम जिसमें पायथन में दिए गए सबस्ट्रिंग शामिल हैं

मान लीजिए कि हमारे पास दो तार s और t हैं, हमें s में न्यूनतम सबस्ट्रिंग का आकार खोजना होगा जिसमें t के सभी वर्ण हों। यदि ऐसा कोई विकल्प मौजूद नहीं है तो -1 लौटाएं।

इसलिए, यदि इनपुट s ="thegrumpywizardmakes" t ="वेक" जैसा है, तो आउटपुट 10 होगा, क्योंकि "वेक" वाला सबसे छोटा विकल्प "विज़ार्डमेक" (10 की लंबाई) है।

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

काउंटर:=बी में प्रत्येक वर्ण की आवृत्ति
प्रारंभ:=0
min_subs :=inf
रेम:=बी में अलग-अलग वर्णों की गिनती
0 से ए के आकार के अंत के लिए, करें
- वर्तमान:=एक [अंत]
- अगर करंट काउंटर में है, तो
  - काउंटर [वर्तमान]:=काउंटर [वर्तमान] - 1
  - अगर काउंटर [करंट] 0 के समान है, तो
    - रेम :=रेम - 1
- जबकि रेम 0 के समान है, करें
  - prev_char :=a[शुरू]
  - अगर prev_char काउंटर में है, तो
    - काउंटर [prev_char] :=काउंटर[prev_char] + 1
    - अगर काउंटर [prev_char]> 0, तो
      - रेम :=रेम + 1
  - min_subs :=न्यूनतम min_subs और (अंत - प्रारंभ + 1)
  - प्रारंभ:=प्रारंभ + 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"