Sliding window is not only the index offset

The sliding window MUST operate within a single loop! Every time adjusting only one index per iteration! Never move both simultaneously otherwise it will be O(n^2)!

https://github.com/gou7ma7/leetcode/blob/master/3.%20Longest%20Substring%20Without%20Repeating%20Characters.py

Background

Very funny, I just unexpectlly find out that it is 3rd of Leetcode, but I only remembered that it should be resolved by sliding window.

Topic

A sliding window is not merely defined by two numerical index: the left offset and the right offset.

Intuitive version

We init left and right index, and between string[left: right] slide is the windows, this is very intuitive.

def intuitive(s):
    len_s = len(s) - 1
    if len_s < 2:
        if len_s < 1:
            return 0, ''
        return 1, s[0] if s[0] == s[1] else 2, s
    left = right = 0
    len_s = len(s) - 1
    result_substring = ''
    max_len = 1
    record_set = set()
    while left < len_s - 1:
        if s[right] not in record_set:
            if max_len <= right + 1 - left:
                result_substring = s[left: right+1]
                max_len = right + 1 - left
            
            record_set.add(s[right])
            if right < len_s:
                right += 1
            else:
                break
        else:
            record_set.remove(s[left])
            left += 1
        
        
    return max_len, result_substring

The coding process is so smoothly, it must be that I was too NERVOUS to coding a O(n^3) algorithm.

What A STUPID man!

The window slide only in a loop, move right and left should be in a same leveled loop!

That time I got a outter loop to move right, and another inner loop to move left, and what is more, maintain a s[now_left: now_right+1] to check whether it contains duplicate char each loop.

With above code, it seems that it should a Medium…

And with replacing record_set -> record_dict, it IS O(n) now.

It’s over. All is lost.

Slide with record

In above code, you can see that the set()/dict() is always add a element and move the same one, and what is more, there are so many break when right < len and now char not in record_dict, so we could use a dict to record index, and reassign it to means “Oh, now window contains repeated char, we should slide it to get a new window”.

But the time complex is same as intuitive version, just substract some branch, if nervious, just use initial version!

def slide_with_record(s):
    left = 0
    max_right = 0
    max_len = 0
    record_dict = {}  # Did you see that the above set is always remove and add a same char, so can I combine the too action?
    for right, char in enumerate(s):
        if char in record_dict and record_dict[char] >= left:  # now turn get repeat, so the len of windows won't increase, only slide left
            
            left = record_dict[char] + 1
        
        # slide the repeated char's left to now + 1 to count window if next this repeated char appear again. (if appear is not the char, of cause ignore the char's left index, it will count itself's left index)
        record_dict[char] = right
        if max_len <= right - left + 1:
            max_len = right - left + 1
            max_right = right

    return max_len, s[max_right - max_len + 1: max_right + 1]