Faangprep Logo
LoginRegister
Sliding Window
Medium

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.

  1. Initialize left = 0 and max_len = 0.
  2. Use a map to store the most recent index of each character.
  3. 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).
  4. 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...

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

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.

Start Your Premium Prep