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

🟠   🔖  哈希表 字符串 滑动窗口  🔗 力扣 LeetCode

题目

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

题目大意

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

子字符串 是字符串中连续的 非空 字符序列。

解题思路

这一题可以使用 滑动窗口 技巧来解决。

1. 定义滑动窗口：

   • 使用两个指针 left 和 right 来表示滑动窗口的左右边界。滑动窗口会随着指针的移动而扩大或收缩。
   • 维护一个 window 对象，记录当前窗口中各字符出现的频次。

2. 扩展右指针：

   • 每次将右指针 right 向右移动一格，将对应的字符加入 window，更新该字符的出现次数。

3. 收缩左指针：

   • 如果当前字符已经在窗口中出现了不止一次（即 window[c] > 1），说明当前窗口中有重复字符。此时我们要通过移动左指针 left 来缩小窗口，直到去掉重复的字符，保证窗口内每个字符只出现一次。

4. 记录结果：

   • 每次调整完窗口后，检查当前窗口的大小，并更新最长子串的长度 res。

5. 终止条件：

   • 当右指针遍历到字符串的末尾时，循环结束，返回 res 即为最长不含重复字符的子串长度。

详细的滑动窗口答题框架讲解，可阅读 《3.11 滑动窗口》。

复杂度分析

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

  • 外层的 while 循环遍历字符串 s，每个字符最多只会被左指针和右指针访问一次。因此，整个滑动窗口算法的时间复杂度为 O(n)，因为每个字符至多只会被访问两次（一次右指针移动，一次左指针移动）。
  • 更新 window 和比较操作都是常数时间操作 O(1)，不会影响整体复杂度。

• 空间复杂度： O(1)

  • 虽然在 window 中存储字符的频次，但 window 最多只会包含 128 个 ASCII 字符，因此空间复杂度为 O(1)，与字符串 s 的长度无关。
  • 其他变量如 left、right、res 以及中间变量 c 和 d 都只占用常数空间。

代码

滑动窗口框架

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
	let window = {}, // 记录窗口内字符的频次
		left = 0, // 左指针
		right = 0, // 右指针
		res = 0; // 记录最长子串的长度

	// 遍历字符串
	while (right < s.length) {
		let c = s[right]; // 当前右指针指向的字符
		right++; // 右指针向右移动
		window[c] = (window[c] || 0) + 1; // 统计当前字符的频次

		// 如果窗口内有重复字符，收缩窗口
		while (window[c] > 1) {
			let d = s[left]; // 左指针指向的字符
			left++; // 左指针向右移动，缩小窗口
			window[d]--; // 减少窗口内字符频次
		}

		// 更新结果，记录最大长度
		res = Math.max(res, right - left);
	}

	return res; // 返回最长不含重复字符的子串长度
};

简化版

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
	let max = 0;
	let curStr = '';
	for (let i = 0; i < s.length; i++) {
		const char = s.charAt(i);
		const pos = curStr.indexOf(char);
		if (pos !== -1) {
			curStr = curStr.slice(pos + 1, curStr.length);
		}
		curStr += char;
		max = Math.max(max, curStr.length);
	}
	return max;
};

相关题目

题号	标题	题解	标签	难度
159	至多包含两个不同字符的最长子串 🔒		哈希表 字符串 滑动窗口
340	至多包含 K 个不同字符的最长子串 🔒		哈希表 字符串 滑动窗口
992	K 个不同整数的子数组		数组 哈希表 计数 1+
1695	删除子数组的最大得分		数组 哈希表 滑动窗口
2067	等计数子串的数量 🔒		字符串 计数 前缀和
2260	必须拿起的最小连续卡牌数	[✓]	数组 哈希表 滑动窗口
2401	最长优雅子数组		位运算 数组 滑动窗口
2405	子字符串的最优划分		贪心 哈希表 字符串
2799	统计完全子数组的数目		数组 哈希表 滑动窗口
2981	找出出现至少三次的最长特殊子字符串 I		哈希表 字符串 二分查找 2+
2982	找出出现至少三次的最长特殊子字符串 II		哈希表 字符串 二分查找 2+