3. Longest Substring Without Repeating Characters
mediumAsked at RobinhoodGiven a string, find the length of the longest substring without repeating characters. Robinhood asks this to test the sliding-window-with-hash-map pattern — the same shape they use in production for de-duped event streams.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Robinhood loops.
- Glassdoor (2026-Q1)— Robinhood SWE phone-screen reports list this as a recurring sliding-window problem.
- Reddit r/cscareerquestions (2025-11)— Robinhood new-grad onsite trip reports cite this and its k-distinct generalizations.
Problem
Given a string s, find the length of the longest substring without duplicate 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 length 3.
Example 2
s = "bbbbb"1Explanation: The answer is "b" with length 1.
Example 3
s = "pwwkew"3Explanation: The answer is "wke" with length 3.
Approaches
1. Brute-force every substring
For each start i, expand right and check uniqueness via a set.
- Time
- O(n^3)
- Space
- O(min(n, alphabet))
function lengthOfLongestSubstringBrute(s) {
let best = 0;
for (let i = 0; i < s.length; i++) {
const seen = new Set();
for (let j = i; j < s.length; j++) {
if (seen.has(s[j])) break;
seen.add(s[j]);
best = Math.max(best, j - i + 1);
}
}
return best;
}Tradeoff: Cubic in the worst case (n^2 substrings * n for uniqueness if not optimized). Even the n^2 inner-set version is too slow.
2. Sliding window with last-seen map (optimal)
Track the last seen index of each character. Move left forward to max(left, lastSeen + 1) when a duplicate is found.
- Time
- O(n)
- Space
- O(min(n, alphabet))
function lengthOfLongestSubstring(s) {
const lastSeen = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
if (lastSeen.has(s[right]) && lastSeen.get(s[right]) >= left) {
left = lastSeen.get(s[right]) + 1;
}
lastSeen.set(s[right], right);
best = Math.max(best, right - left + 1);
}
return best;
}Tradeoff: O(n) — single pass with O(min(n, alphabet)) extra space. The key insight is jumping left directly to lastSeen+1 instead of one-by-one. This is the answer Robinhood expects.
3. Sliding window with set (slower but cleaner)
Use a set. When you encounter a duplicate, shrink from the left removing chars until the duplicate is out.
- Time
- O(n)
- Space
- O(min(n, alphabet))
function lengthOfLongestSubstringSet(s) {
const seen = new Set();
let left = 0, 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: Still O(n) amortized (each char added/removed once) but has a tighter loop on duplicates. Cleanest version under interview pressure.
Robinhood-specific tips
Robinhood interviewers tolerate either the lastSeen-map version or the set-shrink version, but the lastSeen-map is the more impressive answer because it jumps left directly instead of looping. Articulate the invariant: 'the substring s[left..right] has all distinct chars; on a duplicate, jump left past the previous occurrence.' If they push on space, mention you could use a fixed-size array indexed by char code when the alphabet is bounded.
Common mistakes
- Forgetting the lastSeen >= left guard — a stale entry from before the current window must be ignored.
- Updating left to lastSeen instead of lastSeen + 1 — off-by-one keeps the duplicate in the window.
- Tracking the best substring (start + end) instead of the length when only length is required — wastes time and bug surface.
Follow-up questions
An interviewer at Robinhood may pivot to one of these next:
- Longest Substring with At Most K Distinct Characters (LC 340).
- Longest Substring with At Most Two Distinct Characters (LC 159).
- Longest Substring with Same Letters After K Replacements (LC 424).
- Minimum Window Substring (LC 76).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does the lastSeen-map jump work?
When s[right] was last seen at position p, any window starting at or before p would re-include the duplicate. So left must be at least p+1 to maintain the all-distinct invariant — jumping there directly skips the wasted work of shrinking one char at a time.
When would I use the set-shrink version instead?
When the alphabet is huge and the duplicate-detection loop's tight inner cost matters less than code clarity. Both are O(n) amortized — interviewers don't penalize either.
Free learning resources
Curated free links for this problem.