3. Longest Substring Without Repeating Characters

🟠   🔖  哈希表 字符串 滑动窗口  🔗 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 ，请你找出其中不含有重复字符的 最长子串 的长度。

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

解题思路

这一题和 第 438 题，第 76 题，第 567 题 类似，用的思想都是"滑动窗口"。

滑动窗口的右边界不断的右移，只要没有重复的字符，就持续向右扩大窗口边界。一旦出现了重复字符，就需要缩小左边界，直到重复的字符移出了左边界，然后继续移动滑动窗口的右边界。以此类推，每次移动需要计算当前长度，并判断是否需要更新最大长度，最终最大的值就是题目中的所求。

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

代码

滑动窗口框架

/**
 * @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;
};

相关题目

相关题目

• 🔒 Longest Substring with At Most Two Distinct Characters
• 🔒 Longest Substring with At Most K Distinct Characters
• 992. K 个不同整数的子数组
• 1695. 删除子数组的最大得分
• 🔒 Number of Equal Count Substrings
• 2260. 必须拿起的最小连续卡牌数
• 2401. 最长优雅子数组
• 2405. 子字符串的最优划分
• 2799. Count Complete Subarrays in an Array

- [🔒 Longest Substring with At Most Two Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters)
- [🔒 Longest Substring with At Most K Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters)
- [992. K 个不同整数的子数组](https://leetcode.com/problems/subarrays-with-k-different-integers)
- [1695. 删除子数组的最大得分](https://leetcode.com/problems/maximum-erasure-value)
- [🔒 Number of Equal Count Substrings](https://leetcode.com/problems/number-of-equal-count-substrings)
- [2260. 必须拿起的最小连续卡牌数](https://leetcode.com/problems/minimum-consecutive-cards-to-pick-up)
- [2401. 最长优雅子数组](https://leetcode.com/problems/longest-nice-subarray)
- [2405. 子字符串的最优划分](https://leetcode.com/problems/optimal-partition-of-string)
- [2799. Count Complete Subarrays in an Array](https://leetcode.com/problems/count-complete-subarrays-in-an-array)