5、无重复字符的最长子串

var lengthOfLongestSubstring = function(s) {
  let map = new Map();
  let start = 0; // 窗口开始位置
  let maxLength = 0; // 最长子串的长度

  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      // 如果这个字符已经出现过了，更新start为上一次出现位置+1和当前start之间的较大值
      start = Math.max(map.get(s[i]) + 1, start);
    }
    // 跟新字符最后出现的位置
    map.set(s[i], i);

    // 计算当前无重复子串的长度（i - start + 1），并更新最大长度
    maxLength = Math.max(maxLength, i - start + 1);
  }

  return maxLength;
};

解题思路：

核心思路为构建一个“窗口”，窗口向右滑动右侧边框，当遇到重复字符时将start变为重复字符的索引+1，这样可以将上一个非重复字符串全部跳过，此时start的落点是全新的“非重复字符串”的起点。

• 使用伸缩窗口记录经过的字符串
• 窗口已经划过的字符必定不是重复字符。
• 当遇到窗口内已存在的字符时，start+1
• 当start+1是小于当前start的时候，维持start位置不变
  • 重复字符的上一次出现位置 + 1： 如果当前字符s[i]在之前已经出现过了，根据Map中记录的它上次出现的位置，新的start应该是这个位置加1。比如在处理字符串”abba”时，当第二个’b’遇到时，start应更新为第一个’b’之后的位置，即2。
  • 当前的start值： 为了保证start不会因为遇到之前出现过的字符而回退，我们取start和上述计算值的最大值。这一点非常重要，尤其是在处理类似”abba”这种情况时。当处理到最后一个’a’时，简单地将start设置为第一个’a’之后的位置是错误的，因为这会导致start回退。正确的做法是保留当前的start值，因为它已经比第一个’a’之后的位置更靠后了。