March 24
Longest Substring Without Repeating Characters
How to notice that the problem asks for a window that expands and contracts, not a full restart at every repetition.
Sliding Window Intermediate 20 min TypeScript
Given a string s, return the length of the longest substring without repeating characters.
Example:
Input: s = "abcabcbb"
Output: 3
The longest substring without repetition is "abc", with length 3.
What to notice before coding
- The problem asks for a substring, not a subsequence.
- The answer is a length, so you do not need to return the substring itself.
- Repetition invalidates the current window, but it does not mean restarting from zero.
Common mistakes
- confusing substring with subsequence
- resetting the whole window when a repetition appears and losing work you already did
Step 1 — Understand what invalidates the substring
As long as all characters are unique, the current window stays valid.
The problem starts when a repetition appears.
The question is not "which substring should I test now?".
The real question is:
how do I keep a valid window while walking through the string?
Step 2 — Write the correct baseline
A good baseline is to fix a start and extend the end until a repetition appears:
export function lengthOfLongestSubstring(s: string): number {
let best = 0
for (let start = 0; start < s.length; start += 1) {
const seen = new Set<string>()
for (let end = start; end < s.length; end += 1) {
const char = s[end]
if (seen.has(char)) {
break
}
seen.add(char)
best = Math.max(best, end - start + 1)
}
}
return best
}
It works. But it restarts too much work for every new starting point.
Step 3 — Ask what really needs to leave the window
If right finds a repeated character, do you need to clear everything?
No.
You only need to remove from the left until that character is no longer duplicated.
That is the heart of sliding window.
Step 4 — Expand and contract under one rule
Use:
rightto expandleftto shrink when the rule breaks- a
Hash Setto represent the characters inside the current window
The window only moves forward. It never needs to go backward.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function lengthOfLongestSubstring(s: string): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(min(n, charset))
Solution 1 — Test every start
Good baseline for seeing the rule clearly.
export function lengthOfLongestSubstring(s: string): number {
let best = 0
for (let start = 0; start < s.length; start += 1) {
const seen = new Set<string>()
for (let end = start; end < s.length; end += 1) {
const char = s[end]
if (seen.has(char)) {
break
}
seen.add(char)
best = Math.max(best, end - start + 1)
}
}
return best
}Solution 2 — Sliding window with Hash Set in O(n)
Now the window adjusts without starting over.
export function lengthOfLongestSubstring(s: string): number {
const window = new Set<string>()
let left = 0
let best = 0
for (let right = 0; right < s.length; right += 1) {
const char = s[right]
while (window.has(char)) {
window.delete(s[left])
left += 1
}
window.add(char)
best = Math.max(best, right - left + 1)
}
return best
}Each character enters and leaves the window at most once.
What to say in the interview
A strong short explanation would be:
The baseline tests each starting point and costs
O(n²). The optimized version maintains a window with no repeated characters. I expand withright, and when a duplicate appears I shrink withleftonly as much as needed until the window becomes valid again. That reduces the problem toO(n).
That shows that you:
- understood the rule that invalidates the window
- explained sliding window as controlled movement
- avoided treating the optimization like a blind template
When this pattern shows up again
The same pattern comes back when you need to:
- keep a valid window
- expand while the rule holds
- shrink until a violation is fixed
- count or maximize something inside a moving contiguous range
The point is not memorizing “sliding window = two pointers.”
The point is noticing when the problem is about a contiguous range with a local rule.