src.minimum_window_substring¶

Classes

class src.minimum_window_substring.Solution[source][source]¶

minWindow(s: str, t: str) → str[source]¶

Thought process¶

Problem uses some of the usual things, frequency map to store substring t and the window of s
Key observation, to achieve an \(O(n)\) solutions we observe that we can define the condition of a substring being contained within a window as a single variable have being compared to need, where both variables are numeric counts representing the specific letters of the substring
We keep track of the window size and window start and end indices
Abstractly the problem uses the general sliding window approach, so the r pointer iterates through the loop as normal and the l pointer iterates on a condition
During the iteration we consider 3 main conditions : have != need \(\rightarrow\) expand window , window[c] == subs[c] \(\rightarrow\) increment have, while have == need \(\rightarrow\) move the l pointer and check if we found a new smallest substring