无重复字符的最长子串（LeetCode3）

题目简介

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

示例 1:

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

示例 2:

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

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

暴力解法

思路

暴力解法的基本思想是遍历字符串中的每一个字符，并计算以该字符开头的最长无重复字符子串的长度。为了实现这一点，我们可以使用两个嵌套循环。外层循环用于选择子串的起始字符，内层循环用于扩展子串，直到遇到重复字符为止。在扩展子串的过程中，我们使用一个集合来存储子串中的字符，以便快速判断某个字符是否重复。

代码

/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
  let maxLength = 0;
  for (let i = 0; i < s.length; i++) {
    const set = new Set();
    let length = 0;
    for (let j = i; j < s.length; j++) {
      if (!set.has(s[j])) {
        set.add(s[j]);
        length++;
        maxLength = Math.max(maxLength, length);
      } else {
        break;
      }
    }
  }
  return maxLength;
}

console.log(lengthOfLongestSubstring('aaaaabcdefgca'));  // 输出: 7

双指针解法

思路

双指针解法的基本思想是使用两个指针（left 和 right）来维护一个滑动窗口，窗口内的字符都是不重复的。右指针 (right) 用于扩展窗口，左指针 (left) 用于收缩窗口以确保窗口内的字符不重复。在这个过程中，我们使用一个集合来存储窗口内的字符。

具体步骤如下：

1. 初始化一个空集合和两个指针 left 和 right。
2. 右指针从头到尾遍历字符串。
3. 如果当前字符不在集合中，将其添加到集合中，并更新最长无重复子串的长度。
4. 如果当前字符已经在集合中，说明出现了重复字符，此时需要移动左指针，直到窗口内不包含重复字符为止。
5. 重复上述过程，直到右指针遍历完整个字符串。

代码

/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
  const charSet = new Set();
  let maxLength = 0;
  let left = 0;
  const len = s.length;
  for (let right = 0; right < len; right++) {
    while (charSet.has(s.charAt(right))) {
      charSet.delete(s.charAt(left));
      left++;
    }

    charSet.add(s.charAt(right));
    maxLength = Math.max(maxLength, right - left + 1);
  }
  return maxLength;
}

console.log(lengthOfLongestSubstring('aaaaabcdefgca'));  // 输出: 7

总结

在解决无重复字符的最长子串问题时，我们可以采用两种方法：暴力解法和双指针解法。暴力解法通过遍历所有可能的子串来找到最长的无重复字符子串，虽然简单易懂但效率较低。双指针解法通过维护一个滑动窗口来高效地查找最长无重复字符子串，具有更好的时间复杂度。根据实际情况和字符串长度选择合适的方法，可以有效解决这一问题。