Given a data string and a window size, calculate the moving average. Queue Use a queue to store the window, and maintain a sum. When full, subtract front element and add new element. Note that use long to store intermediate sum, otherwise could overflow. This file contains bidirectional Unicode text that may be interpreted or […]
Given a string and a list of words (words have same length), find all start indices of substrings that are concatenation of all words from the list exactly once. Brute Force For each index in string we check whether the substring starts with this index contains all the words. We use a hashmap store words […]
Summary of “Sliding window substring search framework” can be found here. Minimum Size Subarray Sum This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters class […]
Given a string s and a pattern p (non-empty). Find all substrings in s that is a anagram of pattern p. Two Pointers/Sliding Window First we put char and its count for pattern p in a hash map (toBeFound). Then, having two points maintaining a sliding window. Also maintain a counter. Each time when shift […]
Given an array and an sliding window size, while the window slide through the array, determine the max element within each window. Monotonic Queue Problem Maintain two deque q1 and q2. q1 represents the sliding window (remove() to remove from front and add() to add to the back if exceeds window size k). Think about […]
Given a pattern and a text. Determine whether a permutation of the pattern in the text. “Two Pointers” Substring Framework Solution This is the two pointers “Substring Framework” solution to this problem. To learn more about the substring framework, please visit here. The idea is that we maintain a sliding window with two pointers, and […]
General Framework to Solve Substring Problems Given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-‘substring’-problems Minimum Window Substring (Framework Solution) This is the “substring framework” solution. Core idea is that when each time end pointer […]
Given N flowers. One flower blooms per day. Array flowers[i] gives the flower position (1-based) blooms at i + 1th day. Find the first day where there are k not bloomed flowers between two flowers already bloomed. [Optimal]Two Pointers/Sliding Window Solution Put in another word, we need to find two flowers such that all the […]
Given a string and an integer k, find the longest substring that contains exactly k distinct characters. Sliding Window Solution The idea is to have two pointers traversing through the string. (the right pointer is simply i, which is used to traverse the list). Meanwhile maintain a set to store unique char in the window, […]
bilbo3000.wordpress.com 