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

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

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

示例

示例 1

输入: s = "abcabcbb"

输出: 3

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

示例 2

输入: s = "bbbbb"

输出: 1

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

示例 3

输入: s = "pwwkew"

输出: 3

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

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示

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

代码

javascript

// 3. 无重复字符的最长子串
// https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

export function lengthOfLongestSubstring (s) {
  // 滑动窗口，保存所有不重复的单个子项
  const list = new Set()
  // 右侧指针
  let rightIndex = -1
  // 最大值
  let max = 0

  for (let index = 0; index < s.length; index++) {
    if (index !== 0) {
      // 当前指针增加的时候，需要将前一位的删除，不然遇到相同项就添加不进来了
      list.delete(s[index - 1])
    }

    // 右侧 + 1 小于字符串长度并且滑动窗口内不包含右侧指针的下一个值
    while (rightIndex + 1 < s.length && !list.has(s[rightIndex + 1])) {
      list.add(s[rightIndex + 1])
      rightIndex++
    }

    // 滑动窗口的子项个数最大值
    max = Math.max(max, list.size)
  }

  return max
};

typescript

// 3. 无重复字符的最长子串
// https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

export function lengthOfLongestSubstring (s: string): number {
  // 滑动窗口，保存所有不重复的单个子项
  const list: Set<string> = new Set()
  // 右侧指针
  let rightIndex = -1
  // 最大值
  let max = 0

  for (let index = 0; index < s.length; index++) {
    if (index !== 0) {
      // 当前指针增加的时候，需要将前一位的删除，不然遇到相同项就添加不进来了
      list.delete(s[index - 1])
    }

    // 右侧 + 1 小于字符串长度并且滑动窗口内不包含右侧指针的下一个值
    while (rightIndex + 1 < s.length && !list.has(s[rightIndex + 1])) {
      list.add(s[rightIndex + 1])
      rightIndex++
    }

    // 滑动窗口的子项个数最大值
    max = Math.max(max, list.size)
  }

  return max
};