Longest Substring Without Repeating Characters

Find the length of the longest substring without repeating characters.

10 min read

Solve on LeetCode

Examples

Input:s = "abcabcbb"

Output:3

Explain:

The answer is "abc", with the length of 3.

Input:s = "bbbbb"

Output:1

Explain:

The answer is "b", with the length of 1.

Input:s = "pwwkew"

Output:3

Explain:

The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Problem Understanding

We need to find the length of the longest substring in a given string s that contains no duplicate characters.

A substring is a contiguous sequence of characters. For example, in "abcabcbb", "abc" is a substring, but "acb" is not (it skips characters).

Algorithm Strategy

We use the Sliding Window technique with a Hash Map (or Array for fixed charsets) to track characters in the current window.

Initialize left = 0 and max_len = 0.
Use a map to store the most recent index of each character.
Iterate right from 0 to end of string:
- If s[right] is in map and its index is >= left, it means we found a repeat inside our current window. Move left to map[s[right]] + 1 to skip the previous occurrence.
- Update map[s[right]] to the current right index.
- Update max_len = max(max_len, right - left + 1).
Return max_len.

Key Insight: Instead of shrinking the window one by one, we can jump the left pointer directly past the duplicate character for O(N) efficiency.

Interactive Visualization

Step 1 / 1

Initializing...

Custom Input

Watch how the window expands and jumps the left pointer when a duplicate is found.

Previous Problem

Maximum Sum Subarray of Size K

Next Problem

Longest Repeating Character Replacement

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.