Topic · Sliding WindowMedium
Longest Substring Without Repeating Characters
Understand the problem
Given a string s, find the length of the longest substring without repeating characters.
Examples:
ts
s = "abcabcbb"
output = 3 // "abc" — the longest substring with no repeats
s = "bbbbb"
output = 1 // "b"
s = "pwwkew"
output = 3 // "wke"A substring here is a contiguous segment, not a scattered subsequence.
Characters can be letters, digits, or any Unicode symbol.
Basic approach
O(n²) time, O(min(n, m)) space — m is the size of the character setts
function lengthOfLongestSubstring(s: string): number {
let maxLen = 0
for (let i = 0; i < s.length; i++) {
const seen = new Set<string>()
for (let j = i; j < s.length; j++) {
if (seen.has(s[j])) break // repeated character → stop this substring
seen.add(s[j])
maxLen = Math.max(maxLen, j - i + 1)
}
}
return maxLen
}Why this approach is slow:
Two nested loops check every pair (i, j).
- For a string of 10⁴ characters that is 10⁸ steps.
- It can be trimmed because once [i..j] is known to be valid, you do not need to start over from scratch.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.