Sliding window 理解与运用【英文版】

从一道题目引申出hashtable的用法，由于当时写心得的时候用的是英文， 然后我现在也没有时间去翻译， 但是我觉得总结挺不错的， 希望你们可以喜欢。

Longest Substring Without Repeating Characters - https://leetcode.com/problems/lo ... peating-characters/


Solution:
1. keep a hashtable; key represent character in the string, and val represents the index of that character in that string
2. iterate through the string, and those character to the hashtable
3. when we encounter a existing character in the hashtable, that means we will need to move the left pointer, so that the current character is always

Template:
    def lengthOfLongestSubstring(self, s):
        hashtable = {}
        left = 0
        right = 0
        res = ''
        for i, char in enumerate(s):
            if char in hashtable:
                new_left = hashtable[char] + 1
                while left < new_left:
                    del hashtable[s[left]]
                    left += 1
            hashtable[char] = i
            res = s[left:i+1] if len(res) < (i+1-left) else res
        return len(res)

Tips:
1. Sliding window question is for question that requires substring. We can put this substring into a sliding window, and have a hashtable that keep tracks of the elements in that sliding window.
2. For sliding window, the question doesn’t require order on the character, that’s why we can just use hashtable as a way to find the right substring. Otherwise, we need to use the LCS (Longest Common Subsequence) to handle those string questions.
3. The core concept of sliding window is that we always keep the current character in that sliding window.  To keep the current character, it might not meet the condition, that’s why we need to move the left pointer to shrink the window to make it meet the conditions.
4. So now the question went from how to find the substring from that condition to how to find the substring and hashtable that satisfy the condition
5. How to find the condition in terms of the hashtable?
    1. Longest substring without repeated character => every time we encounter an existing character, we move the left pointer to hashtable[character] + 1, so now the sling window is valid for the conditions. During the movement/sliding, we also need to clear out some elements in the hashtable since now they are not in sliding window anymore. So the condition becomes ==> character not in hashtable
    2. Longest Repeating character replacement => Notice that this is a different type sliding window question. The above question is about finding the string, and that requires index of that string, but this question doesn’t This question is about finding the longest substring and it’s related to its character counts. So for this sliding window question, we need to keep track of the current sliding window character count. For this question, the condition in terms of the hashtable, we need to make sure the max_count  character in that hashtable has the following relationship: i + 1 - left - max_count <= k;  When our window doesn’t satisfy this condition, we shrink it to make it satisfy this condition. During this process, we can also keep track of the final answer.
    3. Longest Substring with at most K distinct character => This requires us to find the substring and it’s associated with the character count => (sliding window). At most K distinct character ==> len(hashtable) <= k.
    4. Minimum Window Substring => This requires us to find the minimum substring that contains all the characters from the other string. This could essentially be LCS if it requires order/sequence on the characters. The condition for this => count = len(hashtable), have a count that keep track of how many characters we need to find for string2, and then we try to keep the count == 0
    5. Permutation in Strings => This requires use to find the exact length of substring in string1 that contains all the characters from string2, very similar to minimum window substring, but the string length is fixed. So we just need to make sure that sliding_window_hashtable matches the sliding window for string2