Simple Python O(N) Sliding Window Explained with Example
O(N) Sliding Window Python Solution with Counter\n\ndef minWindow(self, s: str, t: str) -> str:\n\ttCounter = Counter(t) # counter for t to check with\n\twindow
**O(N) Sliding Window Python Solution with Counter**\n```\ndef minWindow(self, s: str, t: str) -> str:\n\ttCounter = Counter(t) # counter for t to check with\n\twindow = Counter() # sliding window\n\tans = "" # answer\n\tlast = 0 # last index in our window\n\tfor i,char in enumerate(s):\n\t\twindow[char] = window.get(char,0)+1 # add this character to our window\n\t\twhile window >= tCounter: # while we have all the necessary characters in our window\n\t\t\tif ans == "" or i - last < len(ans): # if the answer is better than our last one\n\t\t\t\tans = s[last:i+1] # update ans\n\t\t\twindow[s[last]] -= 1 # remove the last element from our counter\n\t\t\tlast += 1 # move the last index forward\n\treturn ans # return answer\n```\n**Explanation**\nThe basic idea of this solution is to use a sliding window, ```window```, to keep track of the elements we are looking at (from ```last``` to ```i```, inclusive). While this window has all the necessary counters (```window >= tCounter```), we update the answer if the length of our window, ```i - last```, is less than the length of the answer. We remove the last character when this is true to see if we can use a shorter window.\n\n**Example**\nTo help understand how this algorithm works, let\'s consider the first example given in the problem:\n```\ns = "ADOBECODEBANC", t = "ABC"\ntCounter = Counter({\'A\': 1, \'B\': 1, \'C\': 1})\n\ni = 0, char = A\nwindow = Counter({\'A\': 1}), from "A"\nwe don\'t have all the characters in tCounter!\n\ni = 1, char = D\nwindow = Counter({\'A\': 1, \'D\': 1}), from "AD"\nwe don\'t have all the characters in tCounter!\n\ni = 2, char = O\nwindow = Counter({\'A\': 1, \'D\': 1, \'O\': 1}), from "ADO"\nwe don\'t have all the characters in tCounter!\n\ni = 3, char = B\nwindow = Counter({\'A\': 1, \'D\': 1, \'O\': 1, \'B\': 1}), from "ADOB"\nwe don\'t have all the characters in tCounter!\n\ni = 4, char = E\nwindow = Counter({\'A\': 1, \'D\': 1, \'O\': 1, \'B\': 1, \'E\': 1}), from "ADOBE"\nwe don\'t have all the characters in tCounter!\n\ni = 5, char = C\nwindow = Counter({\'A\': 1, \'D\': 1, \'O\': 1, \'B\': 1, \'E\': 1, \'C\': 1}), from "ADOBEC"\nthe window contains all necessary elements\nwe need to update our answer now! \u2013\u2013> ans = "ADOBEC"\nremove the last element, "A"\nnow window = Counter({\'D\': 1, \'O\': 1, \'B\': 1, \'E\': 1, \'C\': 1, \'A\': 0}), from "DOBEC"\n\ni = 6, char = O\nwindow = Counter({\'O\': 2, \'D\': 1, \'B\': 1, \'E\': 1, \'C\': 1, \'A\': 0}), from "DOBECO"\nwe don\'t have all the characters in tCounter!\n\ni = 7, char = D\nwindow = Counter({\'D\': 2, \'O\': 2, \'B\': 1, \'E\': 1, \'C\': 1, \'A\': 0}), from "DOBECOD"\nwe don\'t have all the characters in tCounter!\n\ni = 8, char = E\nwindow = Counter({\'D\': 2, \'O\': 2, \'E\': 2, \'B\': 1, \'C\': 1, \'A\': 0}), from "DOBECODE"\nwe don\'t have all the characters in tCounter!\n\ni = 9, char = B\nwindow = Counter({\'D\': 2, \'O\': 2, \'B\': 2, \'E\': 2, \'C\': 1, \'A\': 0}), from "DOBECODEB"\nwe don\'t have all the characters in tCounter!\n\ni = 10, char = A\nwindow = Counter({\'D\': 2, \'O\': 2, \'B\': 2, \'E\': 2, \'A\': 1, \'C\': 1}), from "DOBECODEBA"\nthe window contains all necessary elements\nhowever, the window length is longer than our answer so we don\'t update it\nremove the last element, "D"\nnow window = Counter({\'O\': 2, \'B\': 2, \'E\': 2, \'A\': 1, \'D\': 1, \'C\': 1}), from "OBECODEBA"\n\nthe window contains all necessary elements\nhowever, the window length is longer than our answer so we don\'t update it\nremove the last element, "O"\nnow window = Counter({\'B\': 2, \'E\': 2, \'A\': 1, \'D\': 1, \'O\': 1, \'C\': 1}), from "BECODEBA"\n\nthe window contains all necessary elements\nhowever, the window length is longer than our answer so we don\'t update it\nremove the last element, "B"\nnow window = Counter({\'E\': 2, \'A\': 1, \'D\': 1, \'O\': 1, \'B\': 1, \'C\': 1}), from "ECODEBA"\n\nthe window contains all necessary elements\nhowever, the window length is longer than our answer so we don\'t update it\nremove the last element, "E"\nnow window = Counter({\'A\': 1, \'D\': 1, \'O\': 1, \'B\': 1, \'E\': 1, \'C\': 1}), from "CODEBA"\n\nthe window contains all necessary elements\nwe need to update our answer now! \u2013\u2013> ans = "CODEBA"\nremove the last element, "C"\nnow window = Counter({\'A\': 1, \'D\': 1, \'O\': 1, \'B\': 1, \'E\': 1, \'C\': 0}), from "ODEBA"\n\ni = 11, char = N\nwindow = Counter({\'A\': 1, \'D\': 1, \'O\': 1, \'B\': 1, \'E\': 1, \'N\': 1, \'C\': 0}), from "ODEBAN"\nwe don\'t have all the characters in tCounter!\n\ni = 12, char = C\nwindow = Counter({\'A\': 1, \'D\': 1, \'O\': 1, \'B\': 1, \'E\': 1, \'C\': 1, \'N\': 1}), from "ODEBANC"\nthe window contains all necessary elements\nhowever, the window length is longer than our answer so we don\'t update it\nremove the last element, "O"\nnow window = Counter({\'A\': 1, \'D\': 1, \'B\': 1, \'E\': 1, \'C\': 1, \'N\': 1, \'O\': 0}), from "DEBANC"\n\nthe window contains all necessary elements\nwe need to update our answer now! \u2013\u2013> ans = "DEBANC"\nremove the last element, "D"\nnow window = Counter({\'A\': 1, \'B\': 1, \'E\': 1, \'C\': 1, \'N\': 1, \'D\': 0, \'O\': 0}), from "EBANC"\n\nthe window contains all necessary elements\nwe need to update our answer now! \u2013\u2013> ans = "EBANC"\nremove the last element, "E"\nnow window = Counter({\'A\': 1, \'B\': 1, \'C\': 1, \'N\': 1, \'D\': 0, \'O\': 0, \'E\': 0}), from "BANC"\n\nthe window contains all necessary elements\nwe need to update our answer now! \u2013\u2013> ans = "BANC"\nremove the last element, "B"\nnow window = Counter({\'A\': 1, \'C\': 1, \'N\': 1, \'D\': 0, \'O\': 0, \'B\': 0, \'E\': 0}), from "ANC"\n\nreturn "BANC"\n```
['Sliding Window', 'Python']