Dev Skills
Go·Go for coding rounds

Longest substring without repeating characters

A window with two edges and a map of where each character was last seen. Rune-aware, so it counts characters, not bytes.

Topic 38 of 98 · 5 min to read · 45 min to build
After this topic you can
  • Write a rune-aware sliding window for the longest unique substring.
  • Explain why the j >= start check is needed.
  • Predict start and best at each step for a small string.

The problem

Given a string, return the length of the longest substring with no repeated character. "abcabcbb" gives 3 ("abc").

Brute force first

Try every start i. Extend j to the right with a fresh map[rune]bool, and stop at the first repeat. Track the longest.

O(n²) time (O(n³) if you recheck each substring from scratch), O(k) space. The window never throws away work it has already done.

The approach

Keep a window [start, i] with no repeats. Move i forward one character at a time. If that character was last seen inside the window, move start just past it. The window only ever moves right, so this is O(n) time, and O(k) space for k distinct characters.

window.go
package main
import "fmt"
// longestUnique returns the length, in characters, of the longest substring
// with no repeated character. It works on runes, so "héllo" counts é once.
func longestUnique(s string) int {
	last := make(map[rune]int) // rune -> index of its most recent position
	best, start := 0, 0
	for i, r := range []rune(s) {
		if j, ok := last[r]; ok && j >= start {
			start = j + 1 // jump the left edge past the earlier copy
		}
		last[r] = i
		best = max(best, i-start+1)
	}
	return best
}
func main() {
	fmt.Println(longestUnique("abcabcbb")) // 3 (abc)
	fmt.Println(longestUnique("bbbbb"))    // 1
	fmt.Println(longestUnique("pwwkew"))   // 3 (wke)
	fmt.Println(longestUnique("héllo"))    // 3 (hél)
	fmt.Println(longestUnique(""))         // 0
}

Dry run

"abcabcbb", window [start, i]:

icharlast seenstartwindowbest
0a-0a1
1b-0ab2
2c-0abc3
3a0 (in window)1bca3
4b1 (in window)2cab3
5c2 (in window)3abc3
6b4 (in window)5cb3
7b6 (in window)7b3

Go-specific gotchas

  • `range` over a string gives byte offsets. for i, r := range s jumps i by 2 for é. Here we range over []rune(s) so i counts characters, which makes i-start+1 a length in characters.
  • Check `j >= start`, not just that the rune was seen. A copy from before the window must not move start backwards.
  • Comma-ok again. Index 0 is a real position, so last[r] == 0 cannot mean "not seen".
  • For ASCII-only input, a [128]int array is faster than a map. Say it as an optimisation, after it works.
The short version
  • Two edges; the right one always moves, the left one only jumps forward.
  • Map from character to last index.
  • Ranging over a string gives byte offsets; convert to []rune when you need character positions.
Remember: If the question says "longest/shortest contiguous ... such that", think sliding window.
Build this before moving on
Find the length of the longest substring with at most two distinct characters. Shrink the window from the left when a third one arrives.
Coding challenge · checked by tests
Write longestUnique(s string) int that returns the length, in characters, of the longest substring with no repeated character. Example: "abcabcbb" → 3, "héllo" → 3.

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Find the length of the longest substring with at most two distinct characters. Shrink the window from the left when a third one arrives.
  2. 2Dry run "abba". At i = 3 the a was last seen at index 0. What is start, and why does the j >= start check matter here?
  3. 3Find the maximum sum of any k consecutive numbers ([2 1 5 1 3 2], k = 3 → 9).
Official documentation
Check yourselfTake the Go for coding rounds test