# 48、最长不含重复字符的子字符串 [# 最长不含重复字符的子字符串](https://www.jianshu.com/p/b3731b9890f4) 题目 >请从字符串中找出一个最长的不包含重复字符串的子字符串，计算该最长子字符串的长度。假设字符串中只包含‘a’~‘z’的字符。 例如，在字符串“arabcacfr”中，最长的不含重复字符的子字符串是“acfr”，长度为4。 留意最长子串和子序列不是一个概念。例如对“pwwkew”来说，最长子串是“wke”，“pwke”是其中一个子序列。 思路 用f(i)表示以i位置字符结尾的最长不含重复字符的子字符串的长度，则所求的就是i从0~n-1中最大的一个f(i)。 在遍历数组时，**记录每个字符最后一次出现的位置**。 ①当i号字符之前没有出现过时，f(i)=f(i-1)+1。 ②当之前出现过，且不在f(i-1)指示的子串里出现时，即出现位置到i位置的距离 d>f(i-1)，f(i)=f(i-1)+1。 ③当之前出现过，且就在f(i-1)指示的子串中时，即d<=f(i-1)，这时候f(i)=d。 ``` function lengthOfLongestSubstring (s) { if (!s) { return 0 } let f = [1] let map = new Map() map.set(s[0], 0) let result = [] let max = 0 let indexArr = [] for (let i = 1; i < s.length; i++) { let index = map.get(s[i]) if (index == null) { f[i] = f[i-1] + 1 } else { let d = i - index if (d <= f[i-1]) { f[i] = d } else { f[i] = f[i-1] + 1 } } map.set(s[i], i) if (f[i] === max) { indexArr.push(i) } else if (f[i] > max) { indexArr = [] indexArr.push(i) max = f[i] } } for (let endIndex of indexArr) { result.push(s.slice(endIndex - 3, endIndex + 1)) } return { result, max } } ``` * 准备哈希表 map。key 是 char，value 是 boolean，代表字符 char 是否出现在滑动窗口内 * i 和 j 初始化为 0，结果 ans 初始化为 0 * 检查`s[j]`是否出现过： * 没有出现过，扩大窗口：记录`s[j]`，指针 j 向右滑动一格，更新 ans * 出现过，缩小窗口：指针 i 向右移动一格，`map[s[i]]`更新为 false * 如果 i 和 j 没有越界，回到 step3，否则返回 ans ~~~javascript var lengthOfLongestSubstring = function(s) { const length = s.length; const map = {}; // char => boolean 代表着char是否在目前的窗口内 let i = 0, j = 0; let ans = 0; while (i < length && j < length) { if (!map[s[j]]) { ans = Math.max(j - i + 1, ans); map[s[j]] = true; ++j; } else { // 如果char重复，那么缩小滑动窗口，并更新对应的map map[s[i]] = false; ++i; } } return ans; }; ~~~ ~~~javascript var lengthOfLongestSubstring = function(s) { const length = s.length; const map = new Map(); let i = 0, j = 0; let ans = 0; while (i < length && j < length) { // 容易理解：检查s[j]是否出现过，并且s[j]重复的字符是否在当前的滑动窗口中 if (map.has(s[j]) && map.get(s[j]) >= i) { i = map.get(s[j]) + 1; } ans = Math.max(j - i + 1, ans); map.set(s[j], j); ++j; } return ans; }; ~~~