3. Longest Substring Without Repeating Characters
mediumAsked at AppleLongest Substring Without Repeating Characters is the canonical sliding-window question and Apple's most-repeated string medium. Expand the right pointer; when a duplicate appears, jump the left pointer to last_index_of_dup + 1. The hash-map-of-char-to-last-index variant is what Apple grades on.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Apple loops.
- Glassdoor (2026-Q1)— Apple SWE phone-screen reports list this as the most-repeated sliding-window medium.
- Blind (2025-12)— Apple ICT3/ICT4 reports cite Longest Substring without Repeating Characters as the canonical string medium.
Problem
Given a string s, find the length of the longest substring without repeating characters.
Constraints
0 <= s.length <= 5 * 10^4s consists of English letters, digits, symbols and spaces.
Examples
Example 1
s = "abcabcbb"3Explanation: The answer is 'abc', with the length of 3.
Example 2
s = "bbbbb"1Example 3
s = "pwwkew"3Explanation: Note that the answer must be a substring, 'pwke' is a subsequence and not a substring.
Approaches
1. Sliding window with set, advance left one step at a time
Expand right, adding chars to a set. When a duplicate appears, remove chars from left until the duplicate is gone.
- Time
- O(n)
- Space
- O(min(n, alphabet))
function lengthOfLongestSubstring(s) {
const seen = new Set();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
while (seen.has(s[right])) {
seen.delete(s[left]);
left++;
}
seen.add(s[right]);
best = Math.max(best, right - left + 1);
}
return best;
}Tradeoff: Linear amortized — each char enters and exits the window at most once. The inner while loop can advance left many times in a single right step, but the total left advances across the whole run is bounded by n.
2. Sliding window with last-seen map, jump left (optimal)
Track last seen index per char. When the current char was seen at index >= left, jump left to last_seen + 1.
- Time
- O(n)
- Space
- O(min(n, alphabet))
function lengthOfLongestSubstring(s) {
const lastSeen = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
left = lastSeen.get(ch) + 1;
}
lastSeen.set(ch, right);
best = Math.max(best, right - left + 1);
}
return best;
}Tradeoff: Each right step is O(1) work — no inner loop. The 'jump' replaces the iterative shrink. Apple prefers this version because it's strictly fewer comparisons and the lastSeen >= left check is what makes it correct without resetting the map.
Apple-specific tips
Apple interviewers grade this on the lastSeen >= left invariant. Say it out loud: 'I use a map of char to its last-seen index. A duplicate only matters if it was seen INSIDE the current window — that is, at an index >= left.' That guard is what lets you skip resetting the map between windows and keeps the algorithm truly linear.
Common mistakes
- Forgetting the lastSeen.get(ch) >= left check — jumps left backward when an old duplicate is outside the window.
- Using left = lastSeen.get(ch) (off by one) instead of left = lastSeen.get(ch) + 1.
- Returning the window contents instead of its length.
Follow-up questions
An interviewer at Apple may pivot to one of these next:
- Longest Substring with At Most K Distinct Characters (LC 340) — same window, frequency map.
- Longest Substring with At Most Two Distinct Characters (LC 159).
- Minimum Window Substring (LC 76) — variable window with target counts.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Set + shrink or map + jump?
Same O(n) but the map+jump version does strictly fewer operations and is what Apple expects to see on a senior interview.
Does the alphabet size matter?
For the bound — the space is O(min(n, alphabet)) — yes. For correctness, no; the map handles arbitrary characters.
Free learning resources
Curated free links for this problem.