3. The longest string without repeating characters

The title

Given a string, find the length of the smallest string that does not contain repeating characters. Example 1:

Input:"abcabcbb"Explanation: Because the oldest string without repeating characters is"abc"So its length is 3. Input:"pwwkew"Explanation: Because the oldest string without repeating characters is"wke"So its length is 3. Please note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substringCopy the code

The sliding window

Use Set as a sliding window.

/** * @param {string} s * @return {number} */
var lengthOfLongestSubstring = function(s) {
    const size = s.length
    if(! size)return s
    const subStrSet = new Set(a)// Store window elements for quick weight determination
    let i = 0 // Slide the left edge of the window
    let j = 0 // Slide the right edge of the window
    let len = 0 // Maximum string length

    // Iterate over the string and move the window
    while(i < size && j < size) {
        if(! subStrSet.has(s[j])) {// When a character does not have a set, push it
            // You also need to move the right edge of the sliding window to update the maximum string length
            subStrSet.add(s[j++])
            len = Math.max(len, j-i) // Take len and j-i as the maximum value of the len cache
        } else {
            // Duplicate characters appear if they already exist
            // Remove the string before the repeated character from set, moving the left edge of the sliding window
            [j] [j]
            subStrSet.delete(s[i++])
        }
    }
    return len
};
Copy the code

Time complexity: O(n), worst-case time complexity is O(2n), each character is accessed exactly once by I,j. Space complexity: O(min(m, n)), the space complexity is mainly determined by the Set size, and the Set size is actually determined by the string size N, character Set/letter M. That’s between 0 and n.

Advanced sliding window

In the previous version, the time complexity was O(2n) at worst, with each character accessed by I and j exactly once. The only reason for this problem is that previously if an element s[k] appeared between Windows [I, j], we would constantly remove the previous element from Set, and the element would be repeatedly accessed by a slow left boundary movement via I ++. If s[k] repeats k ‘between Windows [I, j], then we skip [I, k] and change I to k+1.

/** * @param {string} s * @return {number} */
var lengthOfLongestSubstring = function(s) {
    const size = s.length
    if(! size)return s
    const indexMap = new Map(a)// Stores the mapping between character elements and index positions
    let len = 0 // Maximum string length

    // iterate over field s
    // I: window left margin value
    // j: value on the right side of the window
    for (let i = 0, j = 0; j < size; j++) {
        if (indexMap.has(s[j])) {
            // If there is a duplicate element s[I], move the left edge of the window I to the index of the previous element S [I]
            i = Math.max(indexMap.get(s[j]), i)
        }
        len = Math.max(len, j - i + 1) // Max len and j-i+1
        indexMap.set(s[j], j + 1) // select * from s[j] where s[j] = 1
    }
    return len
};
Copy the code

Time complexity O(n). Space complexity O(min(m,n)), where M is the character set size and n is the character size. The following giFs are from the Internet.

advertising

If you think it’s interesting, click on the lower right corner, or pay attention to it directly.