无重复字符的最长子串

滑动窗口问题

介绍

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

示例  1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

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

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

理解

1. 有一个数组，假设有索引 i、j（i < j），求从索引 i 到索引 j 之间有多少个元素。

答案：j - i + 1

2. 定义两个索引，分别代表滑动窗口的左索引和右索引。

循环 n 次，每次循环的轮数 leftIndex 代表左滑块边界的索引。

在一轮循环中，左索引相当于被固定了，移动右索引，求出以该左索引为起点的最长无重复字符子串的长度。

代码

function longestSubstringLength (str: string) {
  // 字符串长度
  const n = str.length
  // 代表最长子串长度
  let longest = 0
  // 代表当前滑动窗口右边界的索引。为 -1 表示还未开始
  let rightIndex = -1
  // 用 Set 保存在窗口内的字符
  const set = new Set()
  // leftIndex 表示滑动窗口左边界的索引。
  for(let leftIndex = 0; leftIndex < n; leftIndex ++) {
    if(leftIndex !== 0) {
      set.delete(str.charAt(leftIndex - 1))
    }
    // 判断下次索引所在的字符是否存在
    while(rightIndex + 1 < n && !set.has(str.charAt(rightIndex + 1))) {
      set.add(str.charAt(rightIndex + 1))
      rightIndex ++
    }
    // max 取最大值
    longest = Math.max(longest, rightIndex - leftIndex + 1)
  }
  return longest
}

// in-source test suites
if (import.meta.vitest) {
  const { it, expect } = import.meta.vitest
  
  it('test1', () => {
    expect(longestSubstringLength('abcabcbb')).toBe(3)
    expect(longestSubstringLength(' ')).toBe(1)
    expect(longestSubstringLength('bbbbb')).toBe(1)
    expect(longestSubstringLength('pwwkew')).toBe(3)
  })
}