One Pager Cheat Sheet

• This lesson introduces the sliding windows algorithm pattern, which usually involves searching for a longest, shortest or optimal sequence that satisfies a given condition, and can be solved in O(N) time and O(1) space complexity.
• The sliding window of size 4 can be seen visually in the image above.
• A sliding window can be used to find the longest substring containing all characters in an ordered data structure.
• The brute force approach to find if a string contains a certain set of characters runs in O(N²) time, while utilizing a sliding window optimizes the process and provides a more efficient solution.
• We need to grow and then shrink our window until we have a valid substring that contains all the characters we are looking for.
• The sliding window technique can be used to find the minimum substring containing all characters in a given set, as demonstrated by the hypothetical example “HGFDSAXZBJKC”.
• The Brute Force approach involves testing all possible substrings of length 4 against the entire string “HGFDSAXZBJKC” and checking if they contain all the necessary characters, with alternate substrings of greater lengths if not, resulting in a time complexity of O(N²).
• We can improve the performance of our solution by using the sliding window technique to break the problem down.
• We view a section of the array by using begin and end pointers to create a "window".
• We need a counter that checks the validity of our current substring and starts with the length of the required characters, decrementing as they get processed.
• We decrement the counter when we encounter a required letter, and if it reaches 0, we know the length is valid.
• The tracker variables for our example of "HGFDSAXZBJKC" and "ABKC" are LStart, LEnd, RStart and REnd.
• We are testing the window by iterating through each letter to find a valid window, using a counter to store the length of the substring and modifying a hash for each letter requirement.
• We decrement our counter variable and modify the dictionary to extend our window until we find the string that fulfills the problem's conditions, which is done by moving the pointers and expanding the scope of the window.
• We are updating the hash map to mark that the character A has been accounted for and adjusting the counter accordingly before stepping into checking the next letter.
• We can shrink our window until we have a valid substring with all the required letters, but no unnecessary ones.
• We shrink and enlarge a window of characters in a string, keeping track of the smallest substring that satisfies certain conditions and then returning it at the end.