JuniorCodeVery commonNot answered yet
Length of the longest substring without repeating characters
Given a string, return the length of the longest substring that contains no repeated character.
Requirements:
- O(n) time — a sliding window, not an O(n²) check of every substring.
- The empty string returns 0; a single character returns 1.
int longestUnique(const std::string& s) {
// your code here
}Write the implementation.
Slide a window with a left pointer and a map of each character's last index. For each right, if the character was seen at or after left, jump left to one past that index. The current window length is right - left + 1; track its maximum. One pass, O(n) time.
- ✗Moving
lefttolastSeen+1even whenlastSeenis before the current window, shrinking it wrongly - ✗Resetting the window from scratch on a repeat, degrading to O(n²)
- ✗Confusing the count of distinct characters with the longest duplicate-free run
- →Why must
leftonly move forward, never backward? - →How would you return the substring itself, not just its length?
Contents
Task
Find the length of the longest substring without repeating characters in O(n) with a sliding window.
Solution
int longestUnique(const std::string& s) {
std::unordered_map<char, int> last; // char -> last index
int left = 0, best = 0;
for (int right = 0; right < static_cast<int>(s.size()); ++right) {
auto it = last.find(s[right]);
if (it != last.end() && it->second >= left)
left = it->second + 1; // move past the duplicate
last[s[right]] = right;
best = std::max(best, right - left + 1);
}
return best;
}Key points
leftmoves only if the duplicate is inside the current window (>= left), else it would go backward.- The window length is
right - left + 1; the maximum is updated each step. - O(n): each character is processed once.
Contents
