Longest Substring Without Repeating Characters
MediumThe problem
Given a string s, return the length of the longest piece of it (a substring: characters next to each other, in order) that has no character appearing twice.
- Example 1Input: s = "abcbdea"Output: 5
The piece "cbdea" has 5 different characters. Any longer piece would repeat the b or the a.
- Example 2Input: s = "aaaa"Output: 1
Every piece longer than 1 repeats the letter a.
- Example 3Input: s = ""Output: 0
An empty string has no characters.
- 0 ≤ s.length ≤ 100,000
- s can contain letters, digits, symbols and spaces
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
When a character repeats inside your window, where must the left edge move to?
The idea
Map char→last index. When the new char was last seen inside the window, jump left to last+1. Record right−left+1.
Target: O(n) time, O(k) space
Go function shape
func lengthOfLongestSubstring(s string) intReference solution
Tested with go test. Try it yourself first, then compare.
// LengthOfLongestSubstring: longest substring without repeating characters.
// Variable window: grow right every step, shrink left while the window is invalid.
func LengthOfLongestSubstring(s string) int {
last := map[byte]int{} // char -> index where it was last seen
best, left := 0, 0
for right := 0; right < len(s); right++ {
if i, seen := last[s[right]]; seen && i >= left {
left = i + 1 // jump past the previous copy: window is valid again
}
last[s[right]] = right
best = max(best, right-left+1)
}
return best
}