Challenge: longest substring without repeating characters
Find the length of the longest substring without repeating characters in O(n) time using a sliding window.
- Find the length of the longest substring without repeating characters in O(n) time
Optional challenge. The efficiency check counts character lookups, so an O(n²) approach is rejected on any input — no timing involved.
Given a string, find the length of the longest substring without repeating
characters. length_of_longest_substring("abcabcbb") → 3 (the substring
"abc"). length_of_longest_substring("bbbbb") → 1.
The brute-force approach checks every possible starting index with an inner loop, giving O(n²). A single-pass sliding window gives O(n).
Hint: use a dict that maps each character to the last index it was seen. When the right pointer encounters a repeated character, jump the left pointer directly past the previous occurrence rather than crawling one step at a time.
Write length_of_longest_substring(s) returning the length of the longest substring with all unique characters. Aim for O(n).
length_of_longest_substring("abcabcbb") → 3length_of_longest_substring("bbbbb") → 1