The title

Answer key

The queue

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function(s) {
    const len = s.length
    const queue = []
    const strArr = [...s]
    let longest = 0
    for (let i = 0; i < len; i++) {
        let existIdx = queue.indexOf(strArr[i])
        if (existIdx > -1) {
            let start = 0
            while (start <= existIdx) {
                queue.shift()
                start++
            }
        }
        queue.push(strArr[i])
        longest = Math.max(queue.length, longest)
    }
    return longest
};
Copy the code

The sliding window

Sliding window is a string or an array of common kind of abstract concepts, the window is in an array or string of the starting index, the ending index series of element collection ([l, r) left closed right away). And the boundary of the sliding window is l, r can move around. If such as moving window to the right one, L +1, r+1.

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function(s) {
    let len = s.length
    // Left edge index
    let l = 0
    // Right edge index
    let r = 0
    let max = 0
    const subStr = [...s]
    const set = new Set(a)while (l < len && r < len) {
        if(! set.has(subStr[r])) { set.add(subStr[r++]) max =Math.max(max, r - l)
        } else {
            set.delete(subStr[l++])
        }
    }
    return max
};
Copy the code

This case is O(2n) at worst, and each character is accessed exactly once by L,r.

Advanced sliding window

In both the previous queue version and the above slide-window version, there is an optimized time complexity of O(2n) at worst, with each character accessed exactly once by L and R. The only reason for this problem is that if an element s[k] appears between Windows [l, r], we would constantly remove the previous element from Set, and the element would be repeatedly accessed by l++ through slow left boundary movement. This step can be accelerated.

The optimized version is to solve the above problem, that is, if s[k] repeats the element k ‘between Windows [L, r], then we directly skip [L, k] and change L to K +1.

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function(s) {
    const len = s.length
    const map = new Map(a)const strArr = [...s]
    let max = 0
    for (let l = 0, r = 0; r < len; r++) {
        if (map.has(strArr[r])) {
            l = Math.max(l, map.get(strArr[r]))
        }
        // r + 1 is used to jump to the next position
        map.set(strArr[r], r + 1)
        max = Math.max(max, r - l + 1)}return max
};
Copy the code

Ps: welcome to pay attention to my public number XYZ programming diary, feel good to help a point 👍, a point to see.