DSA Explained
#3

Longest Substring Without Repeating Characters

Medium
LeetCode

Given a string s, find the length of the longest substring without repeating characters.

💡 In plain English

Imagine picking colored candies from a conveyor belt and putting them into your basket. You want the longest continuous streak of distinct colors. If you grab a color you already have in your basket, you don't dump the whole basket and start from scratch! You simply discard candies from the left until the duplicate color is gone, and then keep picking. The largest basket size you reached at any moment is your answer.

Reference: LeetCode #3 • Longest Substring Without Repeating Characters

Select Viable ApproachExplore how each algorithm moves pointers and handles duplicates
Execution Timeline (Optimal (Map Jump))

Sliding Window Visualizer

Optimal: Sliding Window with Hash Map (Index Jump)
Step 1 / 10
1

Initialize Sliding Window & Map

IN PROGRESS

We initialize left = 0, maxLength = 0, and an empty hash map lastSeen. The map will remember the most recent index where each character appeared.

String s = "abcabcbb"
Current Window: "∅"|Length: 0
a
[0]
↓ L
b
[1]
c
[2]
a
[3]
b
[4]
c
[5]
b
[6]
b
[7]
Active Span: [L: 0, R: —]Starting at index 0 with empty memory.
Hash Map: lastSeen[char]0 keys
{ } Map is empty. No characters recorded yet.
Variable StateLive Registers
left0
right—
maxLength0
Starting at index 0 with empty memory.
1
function lengthOfLongestSubstring(s) {
2
let left = 0;
3
let maxLength = 0;
4
const lastSeen = new Map();
5
for (let right = 0; right < s.length; right++) {
6
const char = s[right];
7
if (lastSeen.has(char) && lastSeen.get(char) >= left) {
8
left = lastSeen.get(char) + 1;
9
}
10
lastSeen.set(char, right);
11
maxLength = Math.max(maxLength, right - left + 1);
12
}
13
return maxLength;
14
}
Optimal (Map Jump) • Synchronized Line TraceLine 2 of 14
→ Executing Statement:Initialize pointers and hash map: let left = 0; const lastSeen = new Map();

Why the Optimal Solution? (Deriving the Approach)

From slow nested loops to a single-pass O(n) sliding window with direct index jumping.

Mental Model Progression
01. StartO(n³) / O(n²)

Brute Force Substrings

Generate every possible substring and check if all characters are distinct using a hash set.

02. BottleneckRepeated Work

Throwing Away Progress

When a duplicate is found at index j, restarting at i + 1 re-verifies characters you already know are unique.

03. Sliding WindowO(2n)

Two-Pointer Window

Expand right pointer. When a duplicate enters, slide left forward until the duplicate drops out.

04. ObservationUnnecessary Steps

Why Slide Slowly?

Advancing left one index at a time in a while loop can take up to n steps if the duplicate is deep inside.

05. OptimalO(n) ✓

Direct Map Jump

Store lastSeen[char] = index. Instantly jump left = max(left, lastSeen[c] + 1) in a single O(1) step!

Complexity Analysis for Optimal (Map Jump)

Time ComplexityO(n)
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)

Each character is visited exactly once by the right pointer. Left pointer directly jumps using the hash map, never backtracking.

Space Complexity (Auxiliary)O(min(n, Σ))
Auxiliary Memory: O(min(n, Σ))

At most min(n, character_set_size) entries stored in the hash map (e.g. 26 lowercase English letters or 128 ASCII symbols).
Explore intuition, examples & complexity analysis below ↓

Brute Force Approach

O(n²) Time

Generate all possible contiguous substrings starting at index i. For each starting point, expand an inner loop j and use a hash set to detect the first repeated character. 

for (let i = 0; i < s.length; i++) {
  const seen = new Set();
  for (let j = i; j < s.length; j++) {
    if (seen.has(s[j])) break;
    seen.add(s[j]);
    maxLength = Math.max(maxLength, j - i + 1);
  }
}
Why it is inefficient:

Whenever a duplicate is hit at index j, the algorithm resets all the way back to i + 1. This discards all knowledge of uniqueness between i + 1 and j - 1, resulting in redundant O(n²) character comparisons.

Optimal Approach: Direct Jump Window

O(n) Time ✓

Maintain a dynamic window [left, right]. Store the most recent index of each character in a Hash Map. When a duplicate s[right] was previously seen inside the window, jump left = lastSeen[char] + 1 immediately! 

for (let right = 0; right < s.length; right++) {
  const char = s[right];
  if (lastSeen.has(char) && lastSeen.get(char) >= left) {
    left = lastSeen.get(char) + 1;
  }
  lastSeen.set(char, right);
  maxLength = Math.max(maxLength, right - left + 1);
}
Why it is optimal:

The right pointer visits each character exactly once, and left only jumps forward in O(1) time. Neither pointer ever backtracks, yielding deterministic single-pass O(n) performance.

Example Test Cases

Official LeetCode Examples
Example 1 (Interleaved Duplicates)
Input: s = "abcabcbb"
Output: 3
The answer is "abc", with the length of 3.
Example 2 (All Identical Characters)
Input: s = "bbbbb"
Output: 1
The answer is "b", with the length of 1.
Example 3 (Substring vs Subsequence)
Input: s = "pwwkew"
Output: 3
The answer is "wke" with length 3. Notice that "pwke" is a subsequence and not a contiguous substring.

Rules & Limits

Constraints
  • String length up to 50,000

    0 ≤ s.length ≤ 5 × 10⁴. An O(n²) approach performs ~1.25 billion operations and will Time Out (TLE).

  • Full ASCII character set

    s consists of English letters, digits, symbols, and spaces.

  • Empty string edge case

    When s = "", the output must be 0.

  • Substrings must be contiguous

    Characters must be strictly adjacent in the original string without skipping.

Key Takeaways & Interview Mental Models

Sliding Window Principles
1. The Window Invariant

Always maintain a clear guarantee: every character between left and right is strictly unique. If a new character violates this invariant, restore it before updating the answer.

2. Don't Forget lastSeen >= left

The hash map keeps historical positions. If a character was seen at index 2, but left is already at index 5, that previous character is outside the active window! Only jump if lastSeen[c] >= left.

3. From O(2n) to O(n)

Both Set-based sliding window and Map-based jumping are asymptotically linear. But index jumping reduces the number of operations from at most 2n down to exactly n, making it the gold standard in competitive programming and interviews.

Related Problems & Sliding Window Practice: Explore All 12 Patterns →
#1 Two Sum (Easy) #2 Add Two Numbers (Medium) #76 Minimum Window Substring (Hard) #424 Longest Repeating Character Replacement (Medium) #159 Longest Substring with At Most Two Distinct Characters (Medium)