[LeetCode 题3] 没有重复字符的最长的子字符串

问题描述

• 输入：一个字符串 s。
• 输出：最长的无重复字符的子串的长度。

示例

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

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

3. 输入: s = "pwwkew" 输出: 3 解释: 最长的无重复字符的子串是 "wke"，长度为 3。

约束条件

• 0 <= s.length <= 5 * 10^4
• 字符串 s 可以包含英文字符、数字、符号和空格。

解决方案

我们可以使用滑动窗口的方法来解决这个问题。滑动窗口是一种常用的算法技巧，用于处理数组或字符串中的子区间问题。具体步骤如下：

通过这种方法，我们可以高效地找到最长的无重复字符子串，时间复杂度为 O(n)，其中 n 是字符串 s 的长度。空间复杂度为 O(min(n, m))，其中 m 是字符集的大小（对于 ASCII 字符集，m 为 128）。

1. 使用两个指针 left 和 right 来表示当前窗口的左右边界。
2. 使用一个哈希集合（Set）来存储当前窗口内的字符，以便快速检查字符是否重复。
3. 移动 right 指针扩展窗口，直到遇到重复字符。
4. 当遇到重复字符时，移动 left 指针收缩窗口，直到窗口内没有重复字符。
5. 在每次移动 right 指针时，更新最长子串的长度。

   function lengthOfLongestSubstring(s) {
     let left = 0;
     let right = 0;
     let maxLength = 0;
     const charSet = new Set();
   
     while (right < s.length) {
       if (!charSet.has(s[right])) {
         // 如果当前字符不在集合中，将其加入集合
         charSet.add(s[right]);
         // 更新最长子串的长度
         maxLength = Math.max(maxLength, right - left + 1);
         // 移动右指针
         right++;
       } else {
         // 如果当前字符在集合中，移除左指针指向的字符
         charSet.delete(s[left]);
         // 移动左指针
         left++;
       }
     }
   
     return maxLength;
   }
   
   // 示例用法
   console.log(lengthOfLongestSubstring("abcabcbb")); // 输出: 3
   console.log(lengthOfLongestSubstring("bbbbb"));    // 输出: 1
   console.log(lengthOfLongestSubstring("pwwkew"));   // 输出: 3

   详细解释

6. 初始化变量：

   • left 和 right 分别表示滑动窗口的左右边界，初始值都为 0。
   • maxLength 用于记录最长无重复字符子串的长度，初始值为 0。
   • charSet 是一个集合，用于存储当前窗口内的字符。

7. 滑动窗口：

   • 使用 while 循环遍历字符串 s，直到 right 指针到达字符串末尾。
   • 如果当前字符 s[right] 不在 charSet 中：
     • 将该字符加入 charSet。
     • 更新 maxLength 为当前窗口的长度 right - left + 1。
     • 移动 right 指针。
   • 如果当前字符 s[right] 已经在 charSet 中：
     • 从 charSet 中移除 s[left]。
     • 移动 left 指针。

8. 返回结果：

   • 返回 maxLength 作为最长无重复字符子串的长度。