Longest Substring Without Repeating Characters
Track the longest contiguous substring whose characters stay unique.
Problem Summary
Original task summary for this archive page. The official LeetCode prompt is linked in the header instead of being mirrored here.
Given a string, find the length of the longest contiguous substring that contains no repeated character.
The important word is substring: the characters must stay contiguous, so this is about maintaining a valid window, not choosing arbitrary characters.
Recognition Pattern
How to notice the underlying interview pattern before writing code.
This is a sliding window with last-seen positions problem.
In interviews, recognize it when:
the question asks for the longest or shortest valid substring
validity depends on character frequencies or duplicates inside a contiguous range
extending the right boundary can break the window, and moving the left boundary can restore it
Key Idea
The main invariant or observation that makes the clean solution work.
Keep a window \([left, right]\) that always contains unique characters.
When you read a new character at position \(right\), check where it last appeared. If that last appearance is still inside the current window, jump \(left\) just past it. Then update the best window length.
This version is cleaner than repeatedly shrinking one step at a time, because it uses the exact information you need: the most recent conflicting index.
Step-by-step Reasoning
How to move from the obvious brute-force idea to the interview-ready solution.
The brute-force solution tries every starting point and grows until a duplicate appears, which leads to \(O(n^2)\) work.
A standard sliding window improves this by expanding right and shrinking left while duplicates exist. That already reaches linear time.
The last-seen optimization makes the window update even cleaner. Instead of removing characters one by one, you jump the left boundary directly to the only place that matters: one position after the previous copy of the repeated character.
The window still moves only forward, which is why the total work stays linear.
Complexity
Time and memory costs for the implementation shown below.
Time: \(O(n)\)
Space: \(O(\min(n, \Sigma))\), where \(\Sigma\) is the character set size
C++ Solution
The exact repository source used for this LeetCode solution page.
#include <algorithm>
#include <array>
#include <string>
class Solution {
public:
int lengthOfLongestSubstring(std::string s) {
std::array<int, 256> lastSeen;
lastSeen.fill(-1);
int bestLength = 0;
int left = 0;
for (int right = 0; right < static_cast<int>(s.size()); ++right) {
const unsigned char current = static_cast<unsigned char>(s[right]);
left = std::max(left, lastSeen[current] + 1);
bestLength = std::max(bestLength, right - left + 1);
lastSeen[current] = right;
}
return bestLength;
}
};
Common Pitfalls
Real implementation mistakes that show up often in interviews and submissions.
Moving the left boundary backward is incorrect. Always use \(left = \max(left, lastSeen[c] + 1)\).
Off-by-one mistakes are common when converting an index range into a length. The current window length is \(right - left + 1\).
If you use an array for character positions in C++, cast to `unsigned char` before indexing to avoid signed-char surprises.
Variants / Follow-ups
Nearby problems and the next generalization to learn once this pattern is stable.
This pattern generalizes to Longest Repeating Character Replacement, Minimum Window Substring, and Longest Substring with At Most K Distinct Characters.
What changes from problem to problem is the window invariant, not the overall left-right scan.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/leetcode/sliding-window/longest-substring-without-repeating-characters/editorial.texC++ implementationcompetitive_programming/leetcode/sliding-window/longest-substring-without-repeating-characters/solution.cppMetadatacompetitive_programming/leetcode/sliding-window/longest-substring-without-repeating-characters/meta.json