Minimum Window Cover
Problem
Given a text and a set of required characters, find the shortest contiguous stretch of the text that contains every required character, counting duplicates. A requirement that lists the same character twice needs two copies inside the stretch. Return the empty text when no stretch qualifies, and the earliest one when several tie for shortest.
Examples
Input: text = "ADOBECODEBANC", need = "ABC"
Output: "BANC"
Why: shorter than ADOBEC, which also covers the requirementInput: text = "aa", need = "aa"
Output: "aa"
Why: duplicates in the requirement must each be matchedInput: text = "a", need = "aa"
Output: ""
Why: edge case, the text cannot supply a second copyHints
0 / 3
The answer is a contiguous stretch, so the search space is a window that can grow on the right and shrink on the left rather than an arbitrary selection.
You need to know at any moment whether the current window already covers the requirement. A tally of how many copies of each character are still owed answers that, and a single counter of unmet copies keeps the check constant time.
Extend the right edge one character at a time, lowering the debt when the character was actually owed. While the debt reaches zero, record the window if it beats the record and then pull the left edge in, raising the debt again if the departing character is now owed. Continue until the right edge reaches the end.
Solution
A window slides forward while a tally holds how many copies of each character it still owes; a character in surplus drops below zero, which is how the tally distinguishes spares from needs. A single counter of outstanding copies makes covered a constant-time test, so the window shrinks from the left as soon as it is valid, recording the best stretch found. Each character enters and leaves the window once. Time is O(n + m), and space is O(k) for the distinct required characters.
from collections import Counter
def minimum_cover(text, need):
if not need:
return ""
owed = Counter(need) # copies of each character still required
missing = len(need) # total outstanding copies
best = (len(text) + 1, 0, 0) # width, start, end of the best window
left = 0
for right, ch in enumerate(text):
if owed[ch] > 0: # this copy was genuinely needed
missing -= 1
owed[ch] -= 1
while missing == 0: # the window covers the requirement
if right - left + 1 < best[0]:
best = (right - left + 1, left, right + 1)
owed[text[left]] += 1 # give the departing character back
if owed[text[left]] > 0:
missing += 1
left += 1
return text[best[1]:best[2]]
print(minimum_cover("ADOBECODEBANC", "ABC")) # -> BANC
print(minimum_cover("aa", "aa")) # -> aa
print(minimum_cover("a", "aa")) # ->Stuck on the idea rather than the code? Sliding Window covers it.