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

示例 1:

输入: s = “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”

输出: 1

解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: s = “pwwkew”

输出: 3

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

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

第一种解法：暴力循环

遍历字符串中的每一个字符，然后把已有的字符放到一个 set 中，直到出现 set 中重复的字符，记录下此时的子串的长度，最后得到最大的子串长度就是结果。但是这种算法的复杂度是O(n^2)。

第二种解法：滑动窗口

有两个指针start和end，end随着遍历字符串慢慢增大，再创建一个用于存放字符的Map，Map的Key就是对应的字符，Value存放的是字符出现的位置+1，意为从这个位置开始到最近出现相同字符的这一串字符是不重复的。这样每次的子串长度就是 end - start + 1，最后比较出一个最大的子串长度就是结果。这种算法的复杂度是O(n)。

var lengthOfLongestSubstring = function(s) {
    let max = 0   //存放最大子串长度
    const map = new Map() //存放字符位置信息
    
    //初始化滑动窗口的左右两端，窗口右端不断增大，窗口左端遇到相同字符的时候收缩
    for (let start = 0, end = 0; end < s.length; end++) { 
        const char = s.charAt(end) //获取当前的字符

        if (map.has(char)) { //如果字符在map中存在，那么缩小窗口
            //将窗口的左边变为上一次该字符出现的位置 + 1
            start = Math.max(start, map.get(char)) 
        }
        //记录字符以及对应的位置
        map.set(char, end + 1)
        
        //比较是否是最大的子串  end - start + 1 即为当前子串的长度
        max = Math.max(end - start + 1, max)
    }

    return max
};

状态演示

示例1: “abcabcbb”

  1. 当前字符为”a”，Map中没有该字符，更新Map { “a” : 1 } ，start为0，end为0，当前子串长度1，最长子串长度1，当前子串为”a”

  2. 当前字符为”b”，Map中没有该字符，更新Map { “a” : 1, “b”: 2 } ，start为0，end为1，当前子串长度2，最长子串长度2，当前子串为”ab”

  3. 当前字符为”c”，Map中没有该字符，更新Map { “a” : 1, “b”: 2, “c”: 3 } ，start为0，end为2，当前子串长度3，最长子串长度3，当前子串为”abc”

  4. 当前字符为”a”，Map中有该字符，更新Map { “a” : 4, “b”: 2, “c”: 3 } ，start为1，end为3，当前子串长度3，最长子串长度3，当前子串为”bca”

  5. 当前字符为”b”，Map中有该字符，更新Map { “a” : 4, “b”: 5, “c”: 3 } ，start为2，end为4，当前子串长度3，最长子串长度3，当前子串为”cab”

  6. 当前字符为”c”，Map中有该字符，更新Map { “a” : 4, “b”: 5, “c”: 6 } ，start为3，end为5，当前子串长度3，最长子串长度3，当前子串为”abc”

  7. 当前字符为”b”，Map中有该字符，更新Map { “a” : 4, “b”: 7, “c”: 6 } ，start为5，end为6，当前子串长度2，最长子串长度3，当前子串为”cb”

  8. 当前字符为”b”，Map中有该字符，更新Map { “a” : 4, “b”: 8, “c”: 6 } ，start为7，end为7，当前子串长度1，最长子串长度3，当前子串为”b”

示例2：”pwwkew”

  1. 当前字符为”p”，Map中没有该字符，更新Map { “p” : 1 } ，start为0，end为0，当前子串长度1，最长子串长度1，当前子串为”p”

  2. 当前字符为”w”，Map中没有该字符，更新Map { “p” : 1, “w”: 2 } ，start为0，end为1，当前子串长度2，最长子串长度2，当前子串为”pw”

  3. 当前字符为”w”，Map中有该字符，更新Map { “p” : 1, “w”: 3 } ，start为2，end为2，当前子串长度1，最长子串长度2，当前子串为”w”

  4. 当前字符为”k”，Map中没有该字符，更新Map { “p” : 1, “w”: 3, “k”: 4 } ，start为2，end为3，当前子串长度2，最长子串长度2，当前子串为”wk”

  5. 当前字符为”e”，Map中没有该字符，更新Map { “p” : 1, “w”: 3, “k”: 4, “e”: 5 } ，start为2，end为4，当前子串长度3，最长子串长度3，当前子串为”wke”

  6. 当前字符为”w”，Map中有该字符，更新Map { “p” : 1, “w”: 6, “k”: 4, “e”: 5 } ，start为3，end为5，当前子串长度3，最长子串长度3，当前子串为”kew”