3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解答

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
   let arr =[],max=0
   for(let i=0;i<s.length;i++) {
       let index = arr.indexOf(s[i])
       if(index !== -1) {
           arr.splice(0,index+1)
       }
       arr.push(s[i])
       max = Math.max(arr.length,max)
   }
   return max
};

时间复杂度为O(n^2)。空间复杂度为O(n)

• 优化的Map

TIP

• 使用 map 来存储当前已经遍历过的字符，key 为字符，value 为下标
• 使用 i 来标记无重复子串开始下标，j 为当前遍历字符下标
• 遍历字符串，判断当前字符是否已经在 map 中存在，存在则更新无重复子串开始下标 i 为相同字符的下一位置，此时从 i 到 j 为最新的无重复子串，更新 max ，将当前字符与下标放入 map 中

最后，返回 max 即可

var lengthOfLongestSubstring = function(s) {
    let map = new Map(), max = 0
    for(let i = 0, j = 0; j < s.length; j++) {
        if(map.has(s[j])) {
            i = Math.max(map.get(s[j]) + 1, i)
        }
        max = Math.max(max, j - i + 1)
        map.set(s[j], j)
    }
    return max
};

时间复杂度，空间复杂度都为O(n)

• 利用滑动窗口，双指针。空间复杂度变为O(1)，时间复杂度为O(n)

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let cache = {}
    let left=0,right=0
    let len = s.length;
    let res = 0
    while(right < len) {
        let rc = s[right]
        right++
        if(cache[rc]) {
            cache[rc] = cache[rc] +1
        } else {
            cache[rc] = 1
        }
        while(cache[rc] > 1) {
            let lc = s[left]
            left++
            if(cache[lc]) {
                cache[lc] = cache[lc] - 1
            }
        }
        res = Math.max(res,right - left)
    }
    return res
};