Longest substring without repeating characters: the sliding window solution

In this article

1. Before you start
2. Why interviewers ask this
3. Longest substring without repeating characters from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one problem in the coding interviews learning path. The interview loop overview shows where a coding round sits beside machine learning coding rounds, system design and behavioral interviews.

Why interviewers ask this

Longest substring without repeating characters checks whether you can replace a nested loop with two pointers that only move forward, and whether you can prove the replacement is correct. A candidate who writes the loop over every start position gets a working answer. A candidate who then explains why each character is visited a bounded number of times, and who tests the repeated-letter edge case, shows the habit the round is looking for.

The problem is short: given a string, return the length of the longest substring in which no character appears twice. For example, "abcdefabcbb" gives 6 (GeeksforGeeks, updated January 2026). A weak answer stops at the brute force loop. A strong answer states its cost, improves it, and names the trap before the interviewer does.

Longest substring without repeating characters from first principles

Sliding window

A sliding window is a range of positions in a sequence, tracked by a left and a right pointer, that grows on the right and shrinks from the left so that each element enters and leaves the range at most once.

Last-seen index

A last-seen index is a dictionary entry that records the most recent position at which each character appeared, so the algorithm can find the previous copy of a character without scanning for it.

In plain words

Picture a strip of paper with a hole cut in it, sliding along a line of letters. Whatever shows through the hole is the window. You push the right edge forward one letter at a time. If the new letter already shows through the hole, you push the left edge forward until the old copy is gone. The longest the hole ever got, with no repeated letter inside, is the answer. The analogy breaks in one place: a real strip slides smoothly, but the left edge here jumps straight to the right place in one move.

Stated precisely: keep a window of positions from left to right, with no repeated character inside it, and a dictionary from each character to the last index where it was seen. Move the right pointer through the string once. When the new character's last index is inside the window, move the left pointer to one past that index. Record the window length after every step and keep the maximum.

Step 1: Start with an empty window and an empty dictionary

The algorithm begins with the left pointer at index 0, the best length at 0 and an empty dictionary. The input is the string; besides the right pointer that walks it, the state is three values. An empty string leaves all three untouched and the answer is 0, which is the first edge case to state aloud. Nothing has been read, so nothing can repeat. You now know the whole state of the algorithm: a left pointer, a dictionary and a best length, beside the right pointer. The dictionary holds one entry per distinct character, so the space is at most the smaller of the string length and the alphabet size.

Step 2: Read the next character and look for an earlier copy

At each step the right pointer reads one character and asks the dictionary where that character was last seen. If the dictionary has no entry, the character is new and the window simply grows. If it has an entry, the algorithm must decide whether that earlier copy is inside the current window or already behind the left edge. A copy behind the left edge is harmless, because the window no longer contains it. This one question is the heart of the algorithm. A dictionary lookup takes constant time on average, as long as the hash function spreads keys well and hashing a key is itself constant time (Python 3.15.1 documentation, read October 2026).

Step 3: Jump the left edge, never move it back

When the earlier copy is at index p and p is at least the left pointer, the new left pointer is p + 1. The condition p is at least left is the line that is easiest to leave out. If the code sets left to p + 1 without comparing, a stale entry from before the window can pull the left edge backwards and the window then contains a repeat again.

On the string abba the buggy version returns 3 instead of 2, and the correct version returns 2.¹ The comparison keeps the left edge moving only forward, which keeps the window free of repeats. It is a correctness rule, not a speed rule: the unguarded version does the same amount of work and returns the wrong answer. The jump costs one comparison and one assignment, so each character still costs a constant amount of work. You now know why the guard exists and why the scan stays linear.

Step 4: Record the index and the best length

After handling the repeat, the algorithm writes the character's new last index, which is the current right position, and updates the best length to the larger of the old best and the current window length, right minus left plus 1. Then the right pointer moves on. At the end of the string, the best length is the answer. On pwwkew the best rises to 2 at index 1 and to 3 at index 4, and it never falls, because it only keeps the maximum. The map in the diagram shows the loop: read a character, test for a copy inside the window, move left past it if found, then record the index and the best.

Text description of the diagram

• Each character costs one lookup, one comparison and at most one jump of the left edge.
• A repeated character inside the window moves the left edge past its earlier copy.

Worked example

The string pwwkew traces the algorithm in six steps. At index 0 the window is p and the best is 1. At index 1 the window is pw and the best is 2. At index 2 the character w repeats; its last index is 1, which is inside the window, so left jumps to 2 and the window is w. At index 3 the window is wk, at index 4 it is wke and the best becomes 3, and at index 5 the character w repeats with its last index 2 inside the window, so left jumps to 3 and the window is kew. The best length is 3.¹

1 · p2 · w3 · Repeat w4 · k5 · e6 · Repeat wReplay

Step-by-step description

1. Window p, length 1.
2. Window pw, length 2.
3. Left jumps to 2: window w.
4. Window wk, length 2.
5. Window wke, length 3.
6. Left jumps to 3: window kew.

• The window after each character of pwwkew is p, pw, w, wk, wke and kew.
• The best length on pwwkew is 3.

The Python below is the solution that produced this trace. It keeps the dictionary last, moves left only forward, and updates the best length on every step.

def length_of_longest_substring(s):
    last = {}              # character -> last index where it was seen
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:   # the earlier copy is inside the window
            left = last[ch] + 1               # jump past it, never backwards
        last[ch] = right
        best = max(best, right - left + 1)
    return best

The code ran against six fixed strings, abcabcbb (3), bbbbb (1), pwwkew (3), the empty string (0), abba (2) and dvdf (3), and every result matched both the expected value and a brute-force check; it also matched brute force on 2,000 random strings of up to 12 letters from a five-letter alphabet.¹

Cost matters too. On a string of n distinct characters, the brute-force loop that tries every start position makes n times n plus 1 over 2 checks, while the window takes n steps. For n = 10, 20, 40 and 80, brute force makes 55, 210, 820 and 3,240 checks and the window makes 10, 20, 40 and 80.¹ On 80 distinct characters brute force makes 3,240 checks and the sliding window makes 80 steps. Doubling the string roughly quadruples the brute-force work and only doubles the window's.

Text description of the diagram

• On 80 distinct characters brute force makes 3,240 checks and the sliding window makes 80 steps.
• Brute force makes n times n plus 1 over 2 checks on a string of n distinct characters.

Trade-offs and edge cases

The sliding window with a last-seen index runs in linear time and uses space proportional to the number of distinct characters, and the main alternative design is a set with a shrinking loop. A set-based version first checks the set: while the set already contains the right character, it removes the left character and moves left forward by one, and only then does it add the right character.

It is also linear, because each character is added once and removed at most once, but it walks the left edge over a repeat one character at a time, where the jump version moves it in a single assignment. GeeksforGeeks lists three versions, the naive loop at quadratic time and two window versions at linear time (GeeksforGeeks, updated January 2026).

Space depends on the alphabet. For lowercase English letters a fixed array of 26 entries works and uses constant space; for any text a dictionary grows with the number of distinct characters. The same source stores last indexes in a fixed array for that reason.

Several edge cases decide the result. An empty string returns 0. A string of one repeated letter returns 1. A string with all distinct characters returns its own length. And the repeat of a character that sits behind the left edge must not move the window, which is the abba case. Dictionary keys must be hashable, and two keys that compare equal must have equal hash values (Python data model, read October 2026), so characters from a string are always safe to use as keys. In the worst case, when every key hashes to the same value, a Python dictionary lookup takes linear time (Python 3.15.1 documentation, read October 2026), so the linear bound is an average-case statement.

How to answer it in an interview

The spoken structure: baseline, the improvement and its invariant, the cost, then the edge cases you will test.

Common mistakes

1. Moving the left pointer without comparing. (wrong) "left = last[ch] + 1 whenever the character was seen." A stale index behind the window pulls left backwards; on abba the answer becomes 3. (right) "left = max(left, last[ch] + 1)" or the explicit comparison with left.
2. Confusing a substring with a subsequence. (wrong) Picking letters that are not next to each other. (right) A substring is contiguous, so the window is a single unbroken range.
3. Calling the set version quadratic. (wrong) "The inner while loop makes it n squared." (right) Each character is added once and removed at most once, so the total work is linear.
4. Forgetting the empty string. (wrong) Returning 1 for an empty input by starting the best at 1. (right) Start the best at 0.
5. Returning the window instead of its length. (wrong) Returning the substring when the question asks for a number. (right) Clarify the output first; the length is right - left + 1.

Follow-up questions

Can you do it in constant space?

For a fixed alphabet, yes: replace the dictionary with an array indexed by the character, such as 26 entries for lowercase letters. The space does not grow with the string, only with the alphabet.

How do you return the substring and not only its length?

Store the left index where the best length was found and return the slice from that left index for best characters. This adds one variable to the loop and does not change the cost.

How does this change for at most k distinct characters?

The window is allowed to hold up to k different characters, so the rule for moving the left edge changes from "no repeat" to "more than k distinct", which usually needs a count per character. The structure of the loop stays the same. The coding interviews guide lists the neighbouring pointer and window problems, and lowest common ancestor applies the same baseline-then-improve routine to a tree.

How does the same window solve minimum window substring?

Minimum window substring asks for the shortest substring of s that contains every character of t, with repeats counted. The window grows on the right until it covers t, then shrinks from the left while it still covers t, recording the shortest cover; a count per character and a count of satisfied characters make each check constant time, so both pointers move forward only and the run is linear in the lengths of s and t.

How do you find the peak order volume within any sliding window of K minutes?

Sort the orders by timestamp, move a right pointer over them, and advance the left pointer while the oldest order in the window is K minutes or more older than the newest. The number of orders in the window after each step is the volume of that K-minute window, and the peak is the largest one, in linear time after the sort.

What happens with Unicode characters?

The algorithm works on whatever units the string indexes. If those units are not what the question means by a character, such as a letter with a combining accent, the answer changes, so state in the interview what a character is.

Sources

1. Length of the longest substring without repeating characters — GeeksforGeeks (page updated 20 January 2026), 20 Jan 2026
2. Time complexity of operations on built-in types (Python 3.15.1 documentation) — Python Software Foundation, 25 Oct 2026
3. Data model: object.__hash__ (Python 3 documentation) — Python Software Foundation, 25 Oct 2026