Lt3. 无重复字符的最长子串、滑动窗口、回溯算法

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

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

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

示例 2:

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

示例 3:

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

思路

借助 map 的回溯

设置一个临时数组存储结果，设置一个 map 存储字符及其下标。遍历字符串，每次遍历都要判断 temp 的 size 是不是比 max 的最大值大，大的话更新 max。如果 temp 中不存在该字符，加入 map。如果存在，将 i 设置为 map 中对应字符的下标加一，将 temp 清空。

滑动窗口及 set

设置滑动窗口的左右边界、窗口最大尺寸记录字段 max、temp Set 记录非重复的子串。
以abcabcbb为例
以 (a)bcabcbb 开始的最长字符串为** (abc)abcbb**
以 a(b)cabcbb 开始的最长字符串为** a(bca)bcbb**
以 ab(c)abcbb 开始的最长字符串为** ab(cab)cbb**
以 abc(a)bcbb 开始的最长字符串为** abc(abc)bb**
以 abca(b)cbb 开始的最长字符串为** abca(bc)bb**
以 abcab(c)bb 开始的最长字符串为** abcab(cb)b**
以 abcabc(b)b 开始的最长字符串为** abcabc(b)b**
以 abcabcb(b) 开始的最长字符串为** abcabcb(b)**
算法过程如下：

1. 每次循环如果非第一个字符，都将 temp 中的当前下标的上一个字符删除。如：指向 a 求得 temp 为 abc，下一次循环指向 b，删除 temp 中的 a 得到 temp 为 bc。
2. 如果 right 小于字符串长度，且 right 指向的字符不在 temp 中，就不断增加右边界的值。直到出现重复字符串或者到达字符串长度。
3. 判断 temp 的 size 是不是比 max 的最大值大，大的话更新 max。

相较上一个方法，可以减少很多不必要的设值、设空、判断最大值过程。

解答

借助 map 的回溯

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  s = s.split("");
  let max = 0;
  let temp = new Map();
  for (let i = 0; i < s.length; i++) {
    if (temp.has(s[i])) {
      i = temp.get(s[i]) + 1;
      temp.clear();
    }
    temp.set(s[i], i);
    max = Math.max(temp.size, max);
  }
  return max;
};

滑动窗口及 set

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  s = s.split("");
  let max = 0,
    left = 0,
    right = 0;
  let temp = new Set();
  for (let i = 0; i < s.length; i++) {
    if (i !== 0) temp.delete(s[i - 1]);
    while (right < s.length && !temp.has(s[right])) {
      temp.add(s[right]);
      right++;
    }
    max = Math.max(temp.size, max);
  }
  return max;
};