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

[mengjian-github]

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

 

示例 1:

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

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

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

[mengjian-github]

最常规的是想到暴力解法，通过枚举所有的字串可能来判断生成最大的无重复子串：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let result = 0;
    let curr = 1;

    for (let i = 0; i < s.length; i++) {
        const arr = [s[i]];
        for (j = i + 1; j < s.length; j++) {
            if (arr.includes(s[j])) {
                break;
            } else {
                curr++;
                arr.push(s[j]);
            }
        }
        result = Math.max(result, curr);
        curr = 1;
    }

    return result;
};

[mengjian-github]

类似于这类字串连续的场景，一个有技巧性的实现是利用双指针形成滑动窗口，从而只需要一次循环就可以完成任务：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let i = 0;
    let j = 0;
    let result = 0;
    const map = new Map();

    while(j < s.length) {
        if (map.has(s[j])) {
            // 已经出现过了，记录当前长度，将i移动到改变i的指针
            result = Math.max(result, j - i);
            i = Math.max(i, map.get(s[j]) + 1);
        } 
        map.set(s[j], j);
        j++;
    }

    return Math.max(result, j - i);
};