Coding · Sliding window
Longest Substring Without Repeating Characters
- Reported in several places
- Medium
- SDE
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
Given a string, return the length of the longest contiguous stretch of it in which no character appears twice. For example, "abcabcbb" gives 3, because "abc" is the longest such stretch. The string may hold letters, digits, symbols and spaces, and can be up to 50,000 characters long.
Restated in our own words, not a quote from Flipkart or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: do I return the length or the substring itself? Is the comparison case sensitive, so that "a" and "A" differ? What is the character set: only ASCII, or arbitrary Unicode? What should an empty string return? How long can the input be?
I will assume I return only the length, comparison is exact and case sensitive, characters are JavaScript string units, the empty string gives 0, and n is up to about 50,000. I will mention that emoji made of two string units would need extra care if the interviewer cares about them.
Brute force
Say the obvious answer and why it is too slow.
The direct approach is to try every start index i and walk right, adding characters to a set until one repeats, then record the length and move on to i + 1.
That is O(n · m) where m is the longest distinct run it explores, and in the worst case, with a large character set, m can approach n, which is O(n²). At 50,000 characters an all-distinct input means about 1.25 billion set operations. Even when the alphabet caps the run length, the method is wasteful: every restart at i + 1 re-verifies characters we already knew were distinct a moment ago. We need a way to remember what the previous window taught us.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(min(n, alphabet))
Keep a window s[left..right] that always contains no repeated character, and move right one step at a time. A map remembers, for every character, the last index where we saw it.
When the new character c arrives, look up its last index p. If p is at least left, then c already lives inside the window, so the window would hold two copies. Any valid window that ends at right cannot contain both p and right, so its start must be p + 1 or later, and the best choice is the earliest allowed start: left = p + 1. We jump in one move instead of nudging left one step at a time. If p is smaller than left, or c was never seen, the old sighting is outside the window and we ignore it. That check is the heart of the problem.
Then record lastSeen[c] = right and compare right - left + 1 with the best length.
The invariant is: after handling right, the window s[left..right] has all-distinct characters and left is as small as that allows. Left only moves forward and right only moves forward, so the work is O(n). The pattern is a variable-size sliding window with a last-seen map. The map operations are average O(1) in JavaScript.
Walk it through
A dry run on the example, step by step.
| right | char | left | window | best |
|---|---|---|---|---|
| 0 | a | 0 | a | 1 |
| 1 | b | 0 | ab | 2 |
| 2 | c | 0 | abc | 3 |
| 3 | a | 1 | bca | 3 |
| 4 | b | 2 | cab | 3 |
| 5 | c | 3 | abc | 3 |
| 6 | b | 5 | cb | 3 |
| 7 | b | 7 | b | 3 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take "abcabcbb". The first three steps read a, b and c, so the window grows to "abc" and the best is 3.
At index 3 the character a was last seen at index 0, which is inside the window starting at 0, so left jumps to 1. The window becomes "bca", length 3. Index 4 (b, last at 1) moves left to 2, and index 5 (c, last at 2) moves left to 3. At index 6 the character b was last seen at index 4, so left jumps to 5 and the window is "cb". At index 7 another b was last seen at 6, so left becomes 7 and the window is "b".
The trace table lists left, the window text and the best so far at each step. The final answer is 3.
The code
Runnable JavaScript, checked against test cases.
function lengthOfLongestSubstring(s) {
const lastSeen = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
const previous = lastSeen.get(char);
if (previous !== undefined && previous >= left) {
left = previous + 1;
}
lastSeen.set(char, right);
best = Math.max(best, right - left + 1);
}
return best;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
The empty string never enters the loop and returns 0. A string of one repeated character, like "bbbbb", moves left on every step and returns 1. A string with no repeats returns its full length.
The tricky case is "abba": at the second b the window shrinks to start at 2, and when the final a arrives its last sighting is index 0, which is now left of the window. Because the code only jumps when the stored index is at least left, it correctly ignores that stale sighting and the answer is 2, not 3. Spaces and symbols are ordinary characters. A character made of two string units, such as some emoji, is counted as two units by this code.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the substring itself, and what extra state do you keep?
- How would you adapt this when at most k distinct characters are allowed instead of none repeated?
- Can you replace the map with a fixed array, and what does that assume about the characters?
- What changes if the input arrives as a stream you cannot rewind?
Where candidates slip
The mistakes this problem punishes.
The most common bug is skipping the "last index is at least left" check, which lets an old sighting drag left backwards and gives "abba" the answer 3. The second is a Set-based version that removes only one character from the left per repeat instead of looping until the repeated character is gone, which leaves a duplicate inside the window and reports too long a length ("abba" gives 3 there too).
Other slips: computing the length as right - left and missing the plus one; updating the best length before moving left; and restarting the scan from the old start plus one after every repeat instead of jumping left, which silently turns the solution back into O(n²).
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.