子串题库

2024年04月09日

柏拉文

越努力，越幸运

一、无重复字符的最长子串

---

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

示例1:

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

示例2:

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

1.1 滑动窗口

思路

一、初始化

1. 创建一个 Set 集合, 用于存储当前窗口内的字符，方便判断是否存在重复。

2. 获取字符串的长度, 用于后续的循环判断。

3. 定义指针和结果变量: rk（right pointer） 初始化为 -1, 表示窗口右边界（开始时窗口为空）; result 用来保存当前找到的最长无重复子串的长度。

二、外层循环（左指针移动）: 使用变量 i 作为左边界的指针, 从字符串开头开始遍历。

1. 当 i 不等于 0 时, 删除前一个位置的字符: 这一步是为了当左边界向右移动时, 保证窗口内只保留从当前左指针开始的字符。原因: 在滑动窗口的过程中,我们希望当前窗口始终只包含从位置 i 到位置 rk 的字符。当左边界 i 右移时，原来窗口的第一个字符（即 str[i-1]）已经不再属于新的窗口范围, 所以需要将其从 Set 中移除。

2. 内层循环（右指针扩张窗口）: 使用 while 循环不断向右扩张窗口, 只要下一个字符不在当前窗口中（即 Set 中不存在），就将它加入 Set, 并移动右指针 rk。

3. 更新最大子串长度: 计算当前窗口的长度, rk - i + 1, 并与 result 取最大值, 保证 result 始终保存最长无重复子串的长度。

实现

function lengthOfLongestSubstring(str) {
  let rk = -1;
  let result = 0;
  const set = new Set();

  for (let i = 0; i < str.length; i++) {
    if (i > 0) {
      set.delete(str[i - 1]);
    }

    while (rk + 1 < str.length && !set.has(str[rk + 1])) {
      set.add(str[rk + 1]);
      rk++;
    }

    result = Math.max(result, rk - i + 1);
  }

  return result;
}

• 时间复杂度: O(N)