Longest Substring Without Repeating Characters: The Sliding Window Technique
The Prompt
Given a string `s`, find the length of the longest substring without repeating characters.
Understanding the Problem
You want the longest stretch of consecutive characters in which nothing repeats. Checking every substring for duplicates is O(n³) — or O(n²) with a set per start index. The key observation: if s[l..r] has no repeats, neither does any substring inside it, so validity is a property you can grow and shrink incrementally.
That is the sliding-window shape: a right pointer extends the window one character at a time, a set tracks exactly what the window contains, and a left pointer evicts characters only when a duplicate forces it to.
The Interview Flow
Interviewer
How would you find the length of the longest substring in a given string that has no repeating characters?
Candidate
This sounds like a job for the sliding window technique. I can maintain a "window" of characters that is my current substring. I will expand this window by moving a right pointer, and I will shrink it by moving a left pointer.
Interviewer
How do you keep track of the characters inside the window and detect duplicates?
Candidate
I can use a hash set or a hash map. As I expand the window with the right pointer, I add the character to the set. If I encounter a character that is already in the set, it means I have a repeat.
Interviewer
What do you do when you find a repeat?
Candidate
When I find a repeat, I need to shrink the window from the left. I will move the left pointer forward, removing the character at the left pointer from my set, until the duplicate character is no longer in the window. Then I can continue expanding the window from the right. At each step of expanding, I update my maximum length found so far.
Interviewer
That approach is correct. Each character will be visited at most twice (by the left and right pointers), so it's an O(n) solution. Please implement it.
Why does a sliding window work here?
The invariant: the window s[left..right] never contains a repeated character. When s[right] would violate it, the only fix is to evict from the left until the older copy of that character is gone — shrinking from anywhere else could not remove the duplicate. So for each right, left settles at the smallest value keeping the window valid, meaning every maximal duplicate-free substring gets measured.
Each character enters the window once and leaves at most once, so the two pointers together do at most 2n moves: O(n) time with O(min(n, alphabet)) space for the set — down from O(n²) restarts.
O(n) Solution using a Sliding Window and a Set
- Initialize a hash set `charSet` to store characters in the current window.
- Initialize a `left` pointer to 0 and `maxLength` to 0.
- Iterate through the string with a `right` pointer from 0 to the end of the string.
- Inside the loop, check if the character `s[right]` is already in `charSet`.
- If it is, it means we have a duplicate. Start a while loop to shrink the window from the left: remove `s[left]` from `charSet` and increment `left` until `s[right]` is no longer in the set.
- After handling any duplicates, add the current character `s[right]` to `charSet`.
- Update `maxLength = max(maxLength, right - left + 1)`.
- After the main loop finishes, return `maxLength`.
Try it yourself
Write your solution and run it against 4 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function lengthOfLongestSubstring(s) {
let charSet = new Set();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
charSet.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}Explanation
Slide the window across s = "abcabcbb" — the answer is 3, from "abc".
1r grows the window freely: 'a', 'b', 'c' are all new. Window length 2 − 0 + 1 = 3 → maxLength = 3.
2r = 3 is a second 'a', so evict from the left: drop s[0] = 'a', l = 1. Window "bca" is valid again — length 3 − 1 + 1 = 3, no improvement.
3Later, r = 6 hits another 'b': l must jump past the old 'b' at index 4, evicting 'a' and 'b' — window shrinks to "cb", length 2. maxLength stays 3, the final answer.
Complexity Analysis
TIME
O(n)
SPACE
O(k)
Finished working through this one?
Mark it complete to track it on your Data Structures path.