Longest substring without repeating characters. Optimal technique and complexity?
Options
- Brute force over all substrings, O(n³)
- Sliding window with a last-seen map, O(n) (Correct option)
- Sort the characters first, O(n log n)
- A DP table over all substring pairs, O(n²)
Answer
Sliding window with a last-seen map, O(n)
Why
A sliding window is a range [left, right] over the string that you grow and shrink instead of restarting.
Move right forward one character at a time. If that character already appears inside the window, move left just past its previous position. Track the best window length.
Each pointer only moves forward, so the total work is O(n).
Remember
Best contiguous substring/subarray → sliding window.