LeetCode 3: Longest Substring Without Repeating Characters (Sliding Window)
LeetCode 3StringHash MapSliding WindowToday we solve LeetCode 3 - Longest Substring Without Repeating Characters, a classic interview problem for mastering sliding window and index bookkeeping.
Source: https://leetcode.com/problems/longest-substring-without-repeating-characters/
English
Problem Summary
Given a string s, find the length of the longest substring (contiguous segment) that contains no repeated characters.
Key Insight
Use a sliding window [left, right] that always remains valid (no duplicates). When we see a repeated character, jump left to one position after that character's last seen index. Never move left backward.
Brute Force and Why Insufficient
Brute force checks every substring and validates uniqueness with a set. There are O(n^2) substrings and each check can cost up to O(n), resulting in O(n^3) worst-case time. Even with optimizations, O(n^2) still times out for long input.
Optimal Algorithm (Step-by-Step)
1) Initialize left = 0, best = 0, and a hash map lastSeen mapping character to latest index.
2) Iterate right from 0 to n-1.
3) Let c = s[right]. If c exists in lastSeen, update left = max(left, lastSeen[c] + 1).
4) Update lastSeen[c] = right.
5) Current valid window length is right - left + 1; update best.
6) Return best.
Complexity Analysis
Time: O(n) because each index is processed once.
Space: O(min(n, charset)) for the hash map.
Common Pitfalls
- Moving left directly to lastSeen[c] + 1 without max, which can move it backward.
- Confusing substring (contiguous) with subsequence (non-contiguous).
- Updating answer before repairing the window.
- Off-by-one in window length calculation; it must be right - left + 1.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, best = 0;
Map<Character, Integer> lastSeen = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen.containsKey(c)) {
left = Math.max(left, lastSeen.get(c) + 1);
}
lastSeen.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
}func lengthOfLongestSubstring(s string) int {
left, best := 0, 0
lastSeen := map[byte]int{}
for right := 0; right < len(s); right++ {
c := s[right]
if idx, ok := lastSeen[c]; ok {
if idx+1 > left {
left = idx + 1
}
}
lastSeen[c] = right
if right-left+1 > best {
best = right - left + 1
}
}
return best
}class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> lastSeen;
int left = 0, best = 0;
for (int right = 0; right < (int)s.size(); ++right) {
char c = s[right];
if (lastSeen.count(c)) {
left = max(left, lastSeen[c] + 1);
}
lastSeen[c] = right;
best = max(best, right - left + 1);
}
return best;
}
};class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
best = 0
last_seen = {}
for right, ch in enumerate(s):
if ch in last_seen:
left = max(left, last_seen[ch] + 1)
last_seen[ch] = right
best = max(best, right - left + 1)
return best/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let left = 0;
let best = 0;
const lastSeen = new Map();
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (lastSeen.has(c)) {
left = Math.max(left, lastSeen.get(c) + 1);
}
lastSeen.set(c, right);
best = Math.max(best, right - left + 1);
}
return best;
};中文
题目概述
给定字符串 s，求不包含重复字符的最长子串（连续子串）长度。
核心思路
维护一个始终合法的滑动窗口 [left, right]。当遇到重复字符时，把 left 跳到该字符上次出现位置的后一位，并且用 max 防止左边界倒退。
暴力解法与不足
暴力法是枚举所有子串并检查是否有重复字符。子串数量是 O(n^2)，每次检查又可能是 O(n)，最坏达到 O(n^3)。数据稍大就不够用。
最优算法（步骤）
1）初始化：left = 0，best = 0，哈希表 lastSeen 记录字符最近出现下标。
2）右指针 right 从左到右扫描字符串。
3）当前字符为 c，若 c 出现过，则 left = max(left, lastSeen[c] + 1)。
4）更新 lastSeen[c] = right。
5）窗口长度为 right - left + 1，更新答案 best。
6）遍历结束返回 best。
复杂度分析
时间复杂度：O(n)（每个位置至多处理一次）。
空间复杂度：O(min(n, 字符集大小))。
常见陷阱
- 更新 left 时忘了取 max，导致左边界回退。
- 把“子串”误写成“子序列”。
- 先算答案再修复窗口，导致答案污染。
- 窗口长度写错，正确是 right - left + 1。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, best = 0;
Map<Character, Integer> lastSeen = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen.containsKey(c)) {
left = Math.max(left, lastSeen.get(c) + 1);
}
lastSeen.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
}func lengthOfLongestSubstring(s string) int {
left, best := 0, 0
lastSeen := map[byte]int{}
for right := 0; right < len(s); right++ {
c := s[right]
if idx, ok := lastSeen[c]; ok {
if idx+1 > left {
left = idx + 1
}
}
lastSeen[c] = right
if right-left+1 > best {
best = right - left + 1
}
}
return best
}class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> lastSeen;
int left = 0, best = 0;
for (int right = 0; right < (int)s.size(); ++right) {
char c = s[right];
if (lastSeen.count(c)) {
left = max(left, lastSeen[c] + 1);
}
lastSeen[c] = right;
best = max(best, right - left + 1);
}
return best;
}
};class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
best = 0
last_seen = {}
for right, ch in enumerate(s):
if ch in last_seen:
left = max(left, last_seen[ch] + 1)
last_seen[ch] = right
best = max(best, right - left + 1)
return best/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let left = 0;
let best = 0;
const lastSeen = new Map();
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (lastSeen.has(c)) {
left = Math.max(left, lastSeen.get(c) + 1);
}
lastSeen.set(c, right);
best = Math.max(best, right - left + 1);
}
return best;
};
Comments