Longest Substring Without Repeating Characters | Sliding Window in JavaScript | Leetcode #3
Some string problems look deceptively simple. You read the string, look for repeating characters, and think: "I'll just keep checking until I find the longest one."
But once the input gets large, that approach quickly becomes expensive.
The real trick is to avoid solving the same problem repeatedly. Instead of restarting every time we encounter a duplicate character, we can maintain a sliding window and move only the boundaries that actually need to change.
1. The Problem
We are given a string s. We need to find the length of the
longest substring without repeating characters.
A substring must contain consecutive characters from the original string.
Example 1
s = "abcabcbb"
The longest substring without repeating characters is:
"abc"
Its length is 3.
Example 2
s = "bbbbb"
The longest valid substring is simply:
"b"
So the answer is 1.
Example 3
s = "pwwkew"
The longest substring without repeating characters is:
"wke"
Therefore, the answer is 3.
2. Naive Thinking
Before jumping into the optimized solution, let's think about the most straightforward approach.
We could start from every character and try to build a substring until we encounter a duplicate.
For example, for:
"abcabcbb"
Start at a:
a → ab → abc → stop at a
Then start at b:
b → bc → bca → stop at b
And continue doing the same for every position.
This works, but we are repeatedly checking characters that we have already processed.
n, this can lead to
O(n²) time.
Can we process the string only once?
Yes. This is where the sliding window technique becomes useful.
3. The Key Insight — Sliding Window
Instead of generating every possible substring, maintain a window between two pointers:
left ---------------- right
Everything between left and right represents
our current substring.
Our goal is to maintain one important rule:
We move right through the string one character at a time.
Whenever the current character has appeared before, we need to move
left forward.
But there is an important optimization.
We don't need to move left one position at a time.
We can remember the last index where every character
appeared.
Then, when a duplicate is found, we can jump directly to:
previousIndex + 1
This is exactly what the Map in our solution does.
4. Visual Walkthrough
Let's walk through:
s = "abcabcbb"
Step 1 — Start
Initially:
left = 0 right = 0 max = 0
We encounter a.
a ↑ window
Store:
a → 0
Current window length:
0 - 0 + 1 = 1
Step 2 — Add b
a b ↑ ↑ L R
b is new, so we simply add it to the map.
Current window:
"ab"
Length = 2.
Step 3 — Add c
a b c ↑ ↑ L R
c is also new.
Current window:
"abc"
Length = 3.
So far:
max = 3
Step 4 — Another a Appears
Now we encounter another a.
a b c a ↑ ↑ L R
The map tells us that the previous a was at index
0.
Therefore, we can move:
left = 0 + 1 left = 1
The new window becomes:
b c a ↑ ↑ L R
Notice what happened.
Instead of removing a, then b, then
c manually, we jumped directly to the correct position.
Step 5 — Another b Appears
The next character is b.
Its previous position was index 1.
So:
left = 1 + 1 left = 2
The window becomes:
c a b
↑
R
Again, the left pointer jumps directly to the correct location.
The Important Detail
There is one subtle condition in the code:
if ((map.get(s[i]) + 1) >= l)
l = map.get(s[i]) + 1;
Why do we need this condition?
Because the previous occurrence of a character might already be outside the current window.
In that situation, moving left backward would break the
sliding window.
Therefore, left should only move forward, never backward.
5. Your Code
Here is the JavaScript solution:
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let map = new Map()
let max = 0
let l = 0
for (let i = 0; i < s.length; i++) {
if (map.has(s[i])) {
if ((map.get(s[i]) + 1) >= l) l = map.get(s[i]) + 1
}
map.set(s[i], i)
max = Math.max(max, i - l + 1)
}
return max
};
Breaking Down the Code
First, we create a Map:
let map = new Map()
This stores each character and its most recent index.
For example:
{
a → 3,
b → 4,
c → 5
}
Next, we maintain:
let max = 0 let l = 0
max stores the longest valid substring found so far.
l represents the left boundary of our sliding window.
The for loop moves the right boundary:
for(let i = 0; i < s.length; i++)
Whenever the character already exists in the map, we check its previous
index and potentially move l.
Finally, the current window length is:
i - l + 1
And we update the answer:
max = Math.max(max, i - l + 1)
6. Edge Cases
A good interview solution should also handle edge cases naturally.
Empty String
s = ""
The loop never executes, so the answer remains:
0
Single Character
s = "a"
There is no duplicate, so the answer is:
1
All Characters Are the Same
s = "aaaaa"
Every new character causes the left pointer to move forward. The longest valid substring is only one character.
Answer: 1
All Characters Are Unique
s = "abcdef"
No duplicate is found, so the window continuously grows.
Answer: 6
7. Complexity
The most important advantage of this solution is that every character is processed only once while the left pointer only moves forward.
Time Complexity
O(n)
where n is the length of the string.
Even though we sometimes move the left pointer, it never moves backward. Across the entire algorithm, both pointers move at most a linear number of times.
Space Complexity
O(min(n, k))
where k represents the number of possible distinct
characters.
In the general case, we can simply describe it as O(n) auxiliary space.
8. How I Would Explain This in an Interview
If asked to explain this solution in an interview, I would keep it simple:
"I use a sliding window to maintain a substring containing only unique characters."
```"I keep two pointers: a left pointer and the current index acting as the right pointer."
"I also use a Map to store the most recent index of every character."
"When I encounter a character that already exists in the Map, I move the left pointer to one position after its previous occurrence."
"However, I only move the left pointer forward because the previous occurrence might already be outside the current window."
"After processing each character, I calculate the current window size and update the maximum. This gives O(n) time complexity."
```9. The Reusable Pattern
The biggest takeaway from this problem isn't just the answer. It's recognizing a pattern.
Whenever you see a problem involving a contiguous substring or subarray with some kind of condition, you should immediately consider the sliding window technique.
Typical signals include:
- Longest substring satisfying a condition
- Shortest substring satisfying a condition
- Subarray with a particular sum or property
- Finding a window with at most K distinct elements
- Finding a window with exactly K distinct elements
- Maintaining frequency/count information inside a range
A common template looks like this:
let left = 0
for (let right = 0; right < n; right++) {
// Add current element
// If window becomes invalid:
// move left until valid again
// Update answer
}In this particular problem, the Map allows us to make the window adjustment even faster by jumping directly to the required position.
10. Conclusion
Longest Substring Without Repeating Characters is a classic problem for learning the sliding window pattern.
The naive approach repeatedly examines overlapping substrings, which leads to unnecessary work.
The optimized solution keeps a dynamic window of unique characters and
uses a Map to remember where each character was last seen.
The most important idea to remember is:
Once this way of thinking becomes familiar, many substring and subarray problems that initially look like O(n²) brute-force problems become straightforward O(n) sliding-window solutions.
Pattern to remember:
Sliding Window + HashMap + Two Pointers
No comments:
Post a Comment