给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
用一个hashmap来建立字符和其出现位置之间的映射。
维护一个滑动窗口,窗口内的都是没有重复的字符,去尽可能的扩大窗口的大小,窗口不停的向右滑动。
(1)如果当前遍历到的字符从未出现过,那么直接扩大右边界;
(2)如果当前遍历到的字符出现过,则缩小窗口(左边索引向右移动),然后继续观察当前遍历到的字符;
(3)重复(1)(2),直到左边索引无法再移动;
(4)维护一个结果res,每次用出现过的窗口大小来更新结果res,最后返回res获取结果。
(图片来自:https://github.com/MisterBooo/LeetCodeAnimation)
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
const mapper = {}; // 记录已经出现过的charactor
let res = 0;
let slidingWindow = [];
for (let c of s) {
if (mapper[c]) {
// 已经出现过了
// 则删除
const delIndex = slidingWindow.findIndex(_c => _c === c);
for (let i = 0 ; i < delIndex; i++) {
mapper[slidingWindow[i]] = false;
}
slidingWindow = slidingWindow.slice(delIndex + 1).concat(c);
} else {
// 新字符
if (slidingWindow.push(c) > res) {
res = slidingWindow.length;
}
}
mapper[c] = true;
}
return res;
};