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
};

测试代码

test

import { expect, test } from 'vitest'
import { lengthOfLongestSubstring } from './typescript.ts'
import { lengthOfLongestSubstring as lengthOfLongestSubstringJs } from './javascript.js'

test(`lengthOfLongestSubstring('abcabcbb') toBe 3`, () => {
  expect(lengthOfLongestSubstring('abcabcbb')).toBe(3)
})

test(`lengthOfLongestSubstring('bbbbb') toBe 1`, () => {
  expect(lengthOfLongestSubstring('bbbbb')).toBe(1)
})

test(`lengthOfLongestSubstring('pwwkew') toBe 3`, () => {
  expect(lengthOfLongestSubstring('pwwkew')).toBe(3)
})


test(`lengthOfLongestSubstringJs('abcabcbb') toBe 3`, () => {
  expect(lengthOfLongestSubstringJs('abcabcbb')).toBe(3)
})

test(`lengthOfLongestSubstringJs('bbbbb') toBe 1`, () => {
  expect(lengthOfLongestSubstringJs('bbbbb')).toBe(1)
})

test(`lengthOfLongestSubstringJs('pwwkew') toBe 3`, () => {
  expect(lengthOfLongestSubstringJs('pwwkew')).toBe(3)
})