Longest Substring Without Repeating Characters

Problem

Given a string s, find the length of the longest substring that contains no repeating characters.

Example

s = "abcabcbb"  ->  3   (the substring "abc")

Go Solution

package main

import "fmt"

func lengthOfLongestSubstring(s string) int {
    last := make(map[byte]int) // char -> last index seen
    start, best := 0, 0

    for i := 0; i < len(s); i++ {
        if j, ok := last[s[i]]; ok && j >= start {
            start = j + 1 // jump the window past the duplicate
        }
        last[s[i]] = i
        if i-start+1 > best {
            best = i - start + 1
        }
    }
    return best
}

func main() {
    fmt.Println(lengthOfLongestSubstring("abcabcbb")) // 3
}

How to Solve

1. Slide a window. Keep a window [start, i] that always holds distinct characters. i expands the window one character at a time.
2. Remember the last position of each character. The map last stores the most recent index where each byte appeared.
3. On a repeat inside the window, move start. If the current character was last seen at index j and j >= start, the duplicate is inside the window, so jump start to j + 1. The j >= start check is essential — an old occurrence already outside the window must be ignored.
4. Track the best length as i - start + 1 after each step.

Complexity

Time: O(n) — each index is visited once and start only moves forward. Space: O(min(n, alphabet)) for the map.