Algorithms and Data Structures · Middle · Question 18 of 75
Longest substring without repeating characters: what's the O(n) idea?
- 1Generate all substrings and check each for duplicates
- ✓Correct answer: On a repeat, move the window's left edge past the old position
- 3Sort the characters and count the longest run of them
Explanation
Store the last index of each character in a map. When the current character was seen inside the window, jump the left edge to last + 1. Each index moves forward only, so the total work is O(n).