DSA Longest Substring Without Repeating Characters

The problem

The problem asks for one length. Find the longest substring in a string where no character repeats, and return its length.

A substring is a run of neighbouring characters. It cannot skip a character. A character may appear many times in the string, but at most once inside the chosen run.

The input is one string. The output is one integer. An empty string has no run at all, so its answer is 0.

cases = [
    ("abcabcbb", 3),
    ("bbbbb", 1),
    ("pwwkew", 3),
    ("dvdf", 3),
    ("", 0),
]
for s, expected in cases:
    print("string", repr(s), "longest:", expected)

Read one row at a time. In abcabcbb the best run is abc, or one of its later copies, so the answer is 3. In bbbbb every character repeats the one before it, so no run passes length 1.

The string dvdf is the subtle row. Its answer is vdf, which starts in the middle of the first attempt. Keep that row in mind for the next section.

Intuition: starting over throws away a good start

A natural first idea scans until a character repeats. It then starts over from the repeated character. The new run begins empty apart from that one character.

Starting over feels clean, and it is wrong. The characters just before the repeat are still distinct from each other and from the repeated character. Most of them can stay.

def restart_longest(s):
    best = 0
    current = ""
    for ch in s:
        if ch in current:
            current = ch
        else:
            current += ch
        best = max(best, len(current))
    return best

print("restart answer for dvdf:", restart_longest("dvdf"))
print("correct answer: 3, from the run vdf")

The restart method reports 2. When the second d arrives, it throws away the v that sat between the two copies of d. The run vdf was there to be kept, and restarting erased it.

The repair is a window that shrinks from the left instead of clearing. Only the part up to the earlier copy has to go. Everything after it stays in the window.

Brute force: check every substring

The straightforward method lists every substring. For each start, it extends the end one character at a time. It keeps a set of the characters inside, and it stops extending once a character repeats.

A set is a collection with no duplicates. Adding a character that is already present marks the end of that start, because every longer substring from the same start repeats it too.

def brute_longest(s):
    best = 0
    checks = 0
    for start in range(len(s)):
        seen = set()
        for end in range(start, len(s)):
            checks += 1
            if s[end] in seen:
                break
            seen.add(s[end])
            best = max(best, end - start + 1)
    return best, checks

for s in ["abcabcbb", "bbbbb", "pwwkew", "dvdf"]:
    best, checks = brute_longest(s)
    print("string", s, "longest:", best, "checks:", checks)

The answers are right. The cost is the repeated work. Each start rescans characters that the previous start already checked, so the checks grow with the square of the length on varied strings.

One observation points to the fix. When a start fails at a repeat, the next useful start is just after the earlier copy of that character. No start in between can do better, and the scan never needs to revisit characters it has passed.

The optimal solution: a window with a last-seen map

The window is the current run of distinct characters. Its right edge grows one character per step. Its left edge only ever moves forward.

The key idea is one sentence. A last-seen map stores the most recent index of each character, and a repeat moves the left edge to just after that stored index, so the window never holds a character twice.

def longest_clean(s):
    last = {}
    left = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last:
            left = max(left, last[ch] + 1)
        last[ch] = i
        best = max(best, i - left + 1)
    return best

for s in ["abcabcbb", "bbbbb", "pwwkew", "dvdf", ""]:
    print("string", repr(s), "longest:", longest_clean(s))

All five cases from the start of the article pass. The empty string passes because the loop never runs, so the best length stays at its starting value of 0.

The max in the left-edge update is a guard, not decoration. A character last seen behind the current window must not drag the left edge backwards. Section 7 shows that case running.

Walkthrough: the window on pwwkew

Follow one string step by step. The second w is the turning point. The left edge jumps past the first w, and the window restarts as a single w at index 2, keeping its right edge where it is.

def trace(s):
    last = {}
    left = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last:
            left = max(left, last[ch] + 1)
        last[ch] = i
        best = max(best, i - left + 1)
        print(i, ch, "window:", s[left:i + 1], "best:", best)
    print("answer:", best)

trace("pwwkew")

The window then grows again through k and e. The final w repeats the w at index 2, so the left edge moves to index 3. The closing window is kew, and the best length stays at 3.

No step ever rescans a character. The left edge moved from 0 to 2 and then to 3 across the whole run, and each move was final.

Complexity

Time is O(n). The right edge visits each character once, the left edge moves forward at most n times in total, and each map lookup is a single step.

Space is O(n) in the worst case. The last-seen map holds one entry per distinct character, and a fully distinct string has n of them.

def window_steps(s):
    last = {}
    left = 0
    steps = 0
    for i, ch in enumerate(s):
        steps += 1
        if ch in last:
            left = max(left, last[ch] + 1)
        last[ch] = i
    return steps

def brute_checks(s):
    checks = 0
    for start in range(len(s)):
        seen = set()
        for end in range(start, len(s)):
            checks += 1
            if s[end] in seen:
                break
            seen.add(s[end])
    return checks

for s in ["abcdefghij", "abcdefghijklmnopqrst", "abcdefghijklmnopqrstuvwxyz0123456789"]:
    print("length", len(s), "window steps:", window_steps(s), "brute checks:", brute_checks(s))

The printed counts separate the two methods cleanly. The window steps equal the length every time. The brute checks follow length times length plus one, over two, on strings with no repeats.

Edge cases and pitfalls

An empty string answers 0, and a string of one repeated character answers 1. A fully distinct string answers its own length, because the left edge never has to move.

The quiet pitfall is a stale last-seen entry. In abba, the final a was last seen at index 0, which is behind the window. Moving the left edge back to index 1 would re-admit the second b and corrupt the window.

def longest_clean(s):
    last = {}
    left = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last:
            left = max(left, last[ch] + 1)
        last[ch] = i
        best = max(best, i - left + 1)
    return best

print("empty:", longest_clean(""))
print("all same:", longest_clean("bbbbb"))
print("all distinct:", longest_clean("abcdef"))
print("stale repeat, abba:", longest_clean("abba"))
print("one character:", longest_clean("x"))

The max guard is what makes the abba case pass. Without it, the left edge moves backwards on the last step, the reported window includes a repeat, and the answer comes out too large.

A second pitfall is updating the best length before shrinking the window. The length is only meaningful once the window is valid again. The code in this article always fixes the left edge first and measures second.