Coding Interview PatternsLongest Substring Without Repeating Characters

MediumTwo Pointers

Longest Substring Without Repeating Characters

Explanation & Solution

Practice Problem

Description

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

A substring is a contiguous non-empty sequence of characters within a string.

Input: s = "abcabcbb"

Output: 3

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

Constraints

0 <= s.length <= 5 * 10⁴
s consists of English letters, digits, symbols, and spaces.

Approach

Two Pointers pattern

1. Initialize a Set and Two Pointers

Create a Set called seen to track characters in the current window
Set left = 0 as the start of the sliding window
Set maxLen = 0 to track the longest substring found so far

2. Expand the Window with the Right Pointer

Iterate right from 0 to s.length - 1
The right pointer represents the end of the current window
Each iteration tries to include s[right] in the current substring

3. Shrink the Window on Duplicate

If s[right] is already in seen, we have a repeating character
Remove s[left] from seen and increment left
Repeat until s[right] is no longer in the set
This shrinks the window from the left to eliminate the duplicate

4. Add the Current Character

After resolving any duplicates, add s[right] to seen
The window [left, right] now contains only unique characters

5. Update the Maximum Length

Compute the current window size: right - left + 1
Update maxLen if this window is larger than the previous best

6. Return the Result

After the loop finishes, maxLen holds the length of the longest substring without repeating characters
Return maxLen

Key Insight

The sliding window technique maintains a window of unique characters. When a duplicate is found, we shrink the window from the left until the duplicate is removed, ensuring every window state contains only unique characters. This avoids the O(n²) brute-force approach of checking every substring.

Time

O(n)each character is added to and removed from the set at most once

Space

O(min(n, m)) — where m is the size of the character set

Visualization

Input:

[a, b, c, a, b, c, b, b]

—

Press ▶ or use ← → to step through

Left (L)Right (R)WindowDone

16 steps

Solution Code

Minimum Window Substring