LeetCode · #3

Longest Substring Without Repeating Characters Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #3

🏗️

Pattern

Sliding Window + Hash Set

Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous sequence of characters within the string — unlike a subsequence, it cannot skip characters.

Example 1

 Input: s = "abcabcbb" Output: 3 // "abc" is the longest substring without repeating characters 

Example 2

 Input: s = "bbbbb" Output: 1 // "b" — every character is the same, so max length is 1 

Example 3

 Input: s = "pwwkew" Output: 3 // "wke" — note that "pwke" is a subsequence, not a substring 

Constraints

 • 0 ≤ s.length ≤ 5 × 10⁴ • s consists of English letters, digits, symbols, and spaces  ↑ ASCII characters — HashSet or int[128] both work 

Section Two · Approach 1

Brute Force — O(n³)

For every possible starting index, expand rightward checking for duplicates. Use a HashSet to verify each substring has no repeats. Track the maximum valid length.

Why it works

Exhaustively considers every substring. For each start, we extend until a duplicate is found, recording the length. Guaranteed to find the longest.

Why we can do better

Problem: When we find a duplicate at position j, we restart from i+1 and rebuild the set from scratch. This throws away all the work from the previous window. A sliding window reuses the previous state — when a duplicate is found, we shrink the left side instead of starting over.

Java — Brute Force

 class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0;
for (int i = 0; i < s.length(); i++) {
HashSet<Character> seen = new HashSet<>();
for (int j = i; j < s.length(); j++) {
if (!seen.add(s.charAt(j))) break;
                max = Math.max(max, j - i + 1);
            }
        }
return max;
    }
}

Python — Brute Force

 class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0 for i in range(len(s)):
            seen = set()
for j in range(i, len(s)):
if s[j] in seen:
break
seen.add(s[j])
                max_len = max(max_len, j - i + 1)
return max_len

Metric	Value
Time	O(n²) best case, O(n³) worst with set rebuild
Space	O(min(n, m)) — where m = character set size

Section Three · Approach 2

Sliding Window + HashSet — O(n)

Maintain a window [left, right] where all characters are unique. Expand right to include a new character. If it's already in the window, shrink from left until the duplicate is removed. Track the maximum window size.

💡 Mental model: Imagine a caterpillar crawling along a string. The head (right pointer) stretches forward, absorbing one character at a time. If the head encounters a character the body already covers, the tail (left pointer) contracts forward, releasing characters until the duplicate is gone. The longest stretch the caterpillar achieves is your answer.

Algorithm — Expanding/contracting window

Step 1: Initialize left = 0, a HashSet, and maxLen = 0.
Step 2: For each right from 0 to n−1:
Step 3: While s[right] is in the set → remove s[left] from set, increment left.
Step 4: Add s[right] to the set.
Step 5: Update maxLen = max(maxLen, right - left + 1).

🎯 When to recognize this pattern:

Any problem asking for the longest/shortest subarray or substring satisfying a condition — think sliding window.
The signals are: (1) contiguous elements, (2) a condition that breaks/restores as the window moves, (3) both pointers only move forward.
This pattern appears in LC 3, LC 76 (Minimum Window Substring), LC 424 (Longest Repeating Character Replacement), LC 567 (Permutation in String), and LC 209 (Minimum Size Subarray Sum).

HashMap optimization:

Instead of shrinking one character at a time, store each character's last seen index in a HashMap.
When a duplicate is found, jump left directly to map.get(c) + 1 — skipping intermediate removals.
This is still O(n) but with a smaller constant factor.

Section Four · Trace

Visual Walkthrough

Trace through s = "abcabcbb":

Sliding Window — expand right, contract left on duplicate

Notice:

Both pointers only move forward. The left pointer advances at most n times total across all iterations.
Combined with the right pointer's n steps, total work is O(2n) = O(n).
Each character enters and leaves the set exactly once.

Section Five · Implementation

Code — Java & Python

Java — Sliding Window + HashSet

 import java.util.HashSet;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> window = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
while (window.contains(s.charAt(right))) // shrink until no dup
window.remove(s.charAt(left++));

            window.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
        }
return maxLen;
    }
}

Python — Sliding Window + set

 class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
        window = set()
        left = max_len = 0 for right in range(len(s)):
while s[right] in window: # shrink until no dup
window.remove(s[left])
                left += 1
window.add(s[right])
            max_len = max(max_len, right - left + 1)
return max_len

Optimized — HashMap (jump left pointer)

Java — HashMap (skip directly to last occurrence + 1)

 import java.util.HashMap;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> lastSeen = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen.containsKey(c) && lastSeen.get(c) >= left)
                left = lastSeen.get(c) + 1; // jump past the duplicate
lastSeen.put(c, right); // update last seen index
maxLen = Math.max(maxLen, right - left + 1);
        }
return maxLen;
    }
}

Python — dict (skip directly)

 class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = max_len = 0 for right, c in enumerate(s):
if c in last_seen and last_seen[c] >= left:
                left = last_seen[c] + 1 # jump past duplicate
last_seen[c] = right
            max_len = max(max_len, right - left + 1)
return max_len

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force (all substrings)	O(n²) to O(n³)	O(min(n,m))	Check every substring; redundant work
Sliding Window + HashSet	O(2n) = O(n)	O(min(n,m))	Each char enters/leaves set at most once
Sliding Window + HashMap ← optimal	O(n)	O(min(n,m))	Jump left pointer; strictly one pass per char

HashSet vs HashMap:

Both are O(n) overall. The HashSet version does at most 2n operations (each char enters and leaves).
The HashMap version does exactly n operations — it never removes characters, just jumps left past the duplicate's last position.
In practice, the difference is small; the HashMap version is a constant-factor improvement.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty string	`""`	Return 0 — no characters, no substring.
Single character	`"a"`	Return 1 — the character itself is the longest substring.
All unique	`"abcdef"`	Entire string is the answer. Window never shrinks. Length = n.
All same	`"aaaa"`	Window is always size 1. Left follows right — every char is a dup of the previous.
Spaces and symbols	`"a b c"`	Spaces are valid characters. "a b c" has all 5 unique chars → length 5.
Duplicate at end	`"abca"`	The window shrinks at the last char. Max was 3 from "abc" — not 4.

⚠ Common Mistake (HashMap version): Forgetting the condition lastSeen.get(c) >= left. Without it, old entries from before the current window can incorrectly trigger a left-pointer jump. If a character was last seen at index 2 but left is already at 5, that old occurrence is outside the window — ignore it. Always check that the last-seen index is within the current window bounds.

← Back to Arrays & Hashing problems

LearningTree

LC 3 · Longest Substring Without Repeating Characters — Solution & Explanation | DSA Guide