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

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

Category	Difficulty	Likes	Dislikes
algorithms	Medium (39.03%)	8417	-

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

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

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

---

Discussion | Solution

思路

使用 map 记录每个字符对应的下标，滑动窗口，当遇到重复的字符时，将窗口左侧设置到该重复的字符第一次出现的右侧。提前剪枝，如果剩余的字符数已经不可能比最大子串大了，那么直接结束即可。

解答

/*
 * @lc app=leetcode.cn id=3 lang=javascript
 *
 * [3] 无重复字符的最长子串
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let res = 0;
  for (let i = 0; i < s.length; i++) {
    if (s.length - i < res) break;

    let temp = new Map();
    let char = s[i],
      index = i;
    while (!temp.has(char) && index < s.length) {
      temp.set(char, index);
      char = s[++index];
    }
    res = Math.max(res, temp.size);
    i = temp.get(char);
  }
  return res;
};
// @lc code=end