What is the optimal approach for Longest Substring Without Repeating Characters?

Use a sliding window with a hash map to track the last index of each character. Move the start pointer when duplicates appear and update max length dynamically.

Why is the sliding window pattern essential for this problem?

It allows linear traversal while maintaining a valid substring without duplicates, avoiding the inefficiency of checking all possible substrings.

How should I handle edge cases like empty or single-character strings?

For empty strings return 0. For single-character strings return 1. The algorithm naturally handles these when initializing pointers and max length.

Can subsequences be considered instead of substrings?

No, only contiguous characters form valid substrings. Non-contiguous sequences like "pwke" in "pwwkew" are invalid for this problem.

What common mistakes occur when updating the window on duplicates?

Common errors include not moving the left pointer correctly past the previous duplicate, double-counting characters, or miscalculating the current window size.

#3

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc" ，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。示例 2: 输入: s = "bbbbb" 输…

哈希表字符串滑动窗口

题目描述

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

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

示例 3:

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

提示：

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

lightbulb

解题思路

方法一：滑动窗口

我们可以用两个指针 $l$ 和 $r$ 维护一个滑动窗口，使其始终满足窗口内没有重复字符，初始时 $l$ 和 $r$ 都指向字符串的第一个字符。用一个哈希表或者长度为 $128$ 的数组 $\textit{cnt}$ 来记录每个字符出现的次数，其中 $\textit{cnt}[c]$ 表示字符 $c$ 出现的次数。

接下来，我们依次移动右指针 $r$ ，每次移动时，将 $\textit{cnt}[s[r]]$ 的值加 $1$ ，然后判断当前窗口 $[l, r]$ 内 $\textit{cnt}[s[r]]$ 是否大于 $1$ ，如果大于 $1$ ，说明当前窗口内有重复字符，我们需要移动左指针 $l$ ，直到窗口内没有重复字符为止。然后，我们更新答案 $\textit{ans} = \max(\textit{ans}, r - l + 1)$ 。

最终，我们返回答案 $\textit{ans}$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串的长度。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 表示字符集，这里 $\Sigma$ 的大小为 $128$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cnt = Counter()
        ans = l = 0
        for r, c in enumerate(s):
            cnt[c] += 1
            while cnt[c] > 1:
                cnt[s[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you recognize the need to update the start pointer when encountering duplicates?
question_mark
Can you explain why a hash map is used instead of nested loops for substring checks?
question_mark
Will you handle edge cases like empty strings or strings with all identical characters?

warning

常见陷阱

外企场景

error
Failing to move the left pointer past the previous duplicate, leading to incorrect max length calculations.
error
Using nested loops to generate substrings instead of a sliding window, resulting in TLE for large inputs.
error
Misinterpreting subsequences as substrings, which causes incorrect results like including non-contiguous characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the longest substring containing at most k distinct characters, extending the sliding window pattern.
arrow_right_alt
Return the actual longest substring without repeating characters instead of just its length.
arrow_right_alt
Compute the number of substrings without repeating characters instead of the maximum length, requiring cumulative counting.

help

常见问题

外企场景

继续练习

#30 串联所有单词的子串 #76 最小覆盖子串 #187 重复的DNA序列