roadmap/sliding-window/Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

MediumAmazonGoogleMetaBloombergMicrosoft

Problem

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

Intuition — the key insight

Sliding window: maintain a window [left, right] with no duplicates using a HashMap storing the last seen index of each character. When a duplicate is found at right, move left to max(left, lastSeen[char]+1).

Approach

Variable sliding window

HashMap char→last index. right pointer expands. When s[right] seen and its last index >= left: jump left to lastSeen+1. Update lastSeen[s[right]]=right. Track max window size.

Complexity

Time

O(n)

Space

O(min(n,alphabet))

Each character processed at most twice (once added, once removed). Map size bounded by alphabet size.

Solution code

Python

def lengthOfLongestSubstring(self, s: str) -> int:
    last_seen = {}  # char -> last index
    left = best = 0
    
    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        best = max(best, right - left + 1)
    
    return best

Edge cases to remember

⚠Empty string: return 0

⚠All same characters: return 1

⚠All unique: return n

Hints

What pattern do you think this problem uses?