Longest Substring Without Repeating Characters

mediumSliding Window50 stepsJava · Python · C++

Grow a window to the right one character at a time. When the new character is already inside the window, jump the left edge just past its previous position. The window always has unique characters, and its widest size is the answer.

▶ Watch the animated trace

Traced input: s = "abcabcbb" → 3. Original problem: neetcode.io/problems/longest-substring-without-duplicates

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(min(n, charset))

Each character is visited once by r; l only jumps forward.

Key idea

last[c] remembers the latest index of each character.
If c was seen inside the window (last[c] >= l), move l to last[c] + 1.
l never moves backward, so use max(l, last[c] + 1).
After fixing l, the window [l, r] has no repeats; record its length.

Common mistakes

Moving l back to an old index when the repeat is outside the window ("abba").
Using a set and removing one character at a time works but is two-pointer O(2n); know both.
Off-by-one: the length is r - l + 1.

Solution

Java

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> last = new HashMap<>();
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        if (last.containsKey(c) && last.get(c) >= l) {
            l = last.get(c) + 1;
        }
        last.put(c, r);
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Python

def lengthOfLongestSubstring(s: str) -> int:
    last = {}
    l = best = 0
    for r, c in enumerate(s):
        if c in last and last[c] >= l:
            l = last[c] + 1
        last[c] = r
        best = max(best, r - l + 1)
    return best

C++

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> last;
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        char c = s[r];
        if (last.count(c) && last[c] >= l) {
            l = last[c] + 1;
        }
        last[c] = r;
        best = max(best, r - l + 1);
    }
    return best;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty string No characters, no window.	`s = ""`	`0`
All the same `l` jumps forward every step.	`s = "bbbbb"`	`1`
Repeat outside the window At the last 'a', its old index 0 is left of `l = 2`, so `l` must not move back.	`s = "abba"`	`2`
Spaces and symbols Every character counts, including the space; all four are distinct.	`s = "a b!"`	`4`
Jump to just after the repeat At the second 'd', `l` moves to 1 (not 2), giving "vdf".	`s = "dvdf"`	`3`