跳到主要内容

3. 无重复字符的最长子串

题目描述​

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

示例 1：

输入：s = "abcabcbb"

输出：3

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

示例 2：

输入：s = "bbbbb"

输出：1

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

示例 3：

输入：s = "pwwkew"

输出：3

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

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

提示：

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

出处：LeetCode

解法一：滑动窗口​

思路​

可以使用滑动窗口来解决这个问题。具体来说，可以维护一个窗口，使得窗口内的字符都是不重复的。可以使用两个指针 left 和 right 分别表示窗口的左右边界。此时，可以使用一个哈希表 map 来存储窗口内的字符及其对应的索引。

代码​

function lengthOfLongestSubstring(s: string): number {
  let left = 0, right = 0;
  let map = new Map<string, number>();
  let ans = 0;

  while (right < s.length) {
    let char = s[right];
    if (map.has(char)) {
      left = Math.max(map.get(char) + 1, left);
    }
    map.set(char, right);
    ans = Math.max(ans, right - left + 1);
    right++;
  }

  return ans;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 表示字符串 s 的长度。
  • 空间复杂度：O(n)O(n)。

解法二：优化的滑动窗口​

思路​

可以对解法一进行优化，使得空间复杂度降为 O(1)O(1)。具体来说，可以使用一个哈希表 map 来存储字符及其对应的索引。此时，可以使用一个指针 left 来表示窗口的左边界。对于每个字符 s[right]，如果 s[right] 在哈希表中已经存在，那么可以直接将 left 移动到 map.get(s[right]) + 1。

代码​

function lengthOfLongestSubstring(s: string): number {
  let left = 0;
  let map = new Map<string, number>();
  let ans = 0;

  for (let right = 0; right < s.length; right++) {
    let char = s[right];
    if (map.has(char)) {
      left = Math.max(map.get(char) + 1, left);
    }
    map.set(char, right);
    ans = Math.max(ans, right - left + 1);
  }

  return ans;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 表示字符串 s 的长度。
  • 空间复杂度：O(1)O(1)。