Longest Substring Without Repeating Characters

Start dumb: try every substring

A substring is contiguous, so the answer is some window [i..j] of the input. The honest first idea is to try them all: for every start i and every end j, check whether s[i..j] has a repeat, and keep the longest clean one.

That check walks the whole candidate, so the total work is O(n³) — or O(n²) if you grow j one step at a time and carry a seen-set with you. On LeetCode’s limit of 5·10⁴ characters, n² is 2.5 billion character touches. Correct, and unusable.

Find the bottleneck

Watch what the brute force actually wastes time on: when the window [i..j] is clean and you extend it to j+1, everything you knew is still true. The only thing that can go wrong is the one new character — s[j+1] colliding with a copy of itself already inside the window. Yet brute force re-verifies the entire window from scratch, re-proving facts it already proved.

The optimal shape

Keep a map from character to the last index where it appeared, and a window [start..end] that is always duplicate-free:

1. Extend end rightward one character at a time.
2. If the new character was last seen inside the window, move start to just past that old copy — one O(1) jump.
3. Record the character’s new position and measure the window.

The map lookup replaces the re-scan; the jump replaces the crawl. Each pointer only ever moves right, so the whole thing is a single pass — O(n) time, O(min(n, alphabet)) space. Don’t take the O(n) on faith: in the player below, watch the start pointer. It never once moves left. That one-directional march is the proof.

Watch it think

Every step below is one forced move of the algorithm. Step through the default input, then break it with your own: empty string, all-same characters (bbbbb), no repeats at all (abcdef), and the abba trap.

1fun lengthOfLongestSubstring(s: String): Int {
2    val lastIndex = HashMap<Char, Int>()
3    var start = 0
4    var best = 0
5    for (end in s.indices) {
6        val c = s[end]
7        val seen = lastIndex[c]
8        if (seen != null && seen >= start) {
9            start = seen + 1
10        }
11        lastIndex[c] = end
12        best = maxOf(best, end - start + 1)
13    }
14    return best
15}