【算法题-困难】无重复字符的最长子串

困难算法题，无重复字符的最长子串，使用 JavaScript 语言编写

题目

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

输入格式

一个字符串 s

输出格式

一个数字，表示最长子串的长度

输入样例

输入样例一：

abcabcbb

输入样例二：

bbbbb

输入样例三：

pwwkew

输出样例

输出样例一：

3

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

输出样例二：

1

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

输出样例三：

3

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

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

分析

详细步骤

1. 初始化：
   • 使用一个哈希表 map 来存储字符及其对应的索引。
   • 初始化两个指针 left 和 right，分别表示当前窗口的左右边界。
   • 初始化变量 maxLength 来记录最长子串的长度。
2. 遍历字符串：
   • 使用 right 指针遍历字符串 s。
   • 如果当前字符 s[right] 已经在哈希表 map 中，并且其索引大于等于 left，则更新 left 为 map[s[right]] + 1。
   • 将当前字符 s[right] 及其索引存入哈希表 map。
   • 计算当前窗口的长度 right - left + 1，并更新 maxLength。
3. 返回结果：
   • 返回 maxLength，即最长不含重复字符的子串的长度。

解答

// 这是题目要求的输入格式
let inputs = `abcabcbb`;

function lengthOfLongestSubstring(s) {
  const hashSet = new Set();
  let right = -1;    // 右指针初始化处于字符串左侧
  let maxLength = 0;
  for (let left = 0; left < s.length; left++) {
    if (left !== 0) {
      // 左指针移动，删掉一个元素
      hashSet.delete(s.charAt(left - 1))
    }
    // console.log("开始移动右指针前", right, left, hashSet);
    while (right + 1 < s.length && !hashSet.has(s.charAt(right + 1))) {
      hashSet.add(s.charAt(++right));
    }
    maxLength = Math.max(maxLength, right - left + 1);
  }
  return maxLength;
}

// 不能 trim，否则无法通过测试用例，因为输入s 由英文字母、数字、符号和空格组成
console.log(lengthOfLongestSubstring(inputs));

解释

1. 初始化：
   • map 用于存储字符及其索引。
   • left 和 right 指针用于表示当前窗口的左右边界。
   • maxLength 用于记录最长子串的长度。
2. 遍历字符串：
   • 遍历字符串 s，使用 right 指针。
   • 如果当前字符 s[right] 已经在 map 中，并且其索引大于等于 left，则更新 left 为 map.get(s[right]) + 1。
   • 将当前字符 s[right] 及其索引存入 map。
   • 计算当前窗口的长度 right - left + 1，并更新 maxLength。
3. 返回结果：
   • 返回 maxLength，即最长不含重复字符的子串的长度。