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

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

उदाहरण के लिए, s = "thegrumpywizardmakes", t = "wake" के लिए आउटपुट 10 होगा (सबस्ट्रिंग "wizardmake")।

एल्गोरिदम (स्लाइडिंग विंडो)

counter := b में प्रत्येक वर्ण की फ्रीक्वेंसी
start := 0, min_subs := inf, rem := b में विशिष्ट वर्णों की संख्या
end = 0 से len(a)-1 तक:
- current := a[end]
- यदि current in counter:
  - counter[current]--
  - यदि counter[current] == 0, तो rem--
- जब rem == 0:
  - prev_char := a[start]
  - यदि prev_char in counter:
    - counter[prev_char]++
    - यदि counter[prev_char] > 0, तो rem++
  - min_subs = min(min_subs, end-start+1)
  - start++
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"