Skip to main content

3. Longest Substring Without Repeating Characters

medium

Find the length of the longest substring containing no repeated characters. The canonical sliding-window-with-hash-map problem and a common interview opener.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

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

Examples

Example 1

Input
s = "abcabcbb"
Output
3

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

Example 2

Input
s = "bbbbb"
Output
1

Explanation: The answer is "b", with length 1.

Example 3

Input
s = "pwwkew"
Output
3

Explanation: The answer is "wke", with length 3. Note that "pwke" is a subsequence and not a substring.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute-force checks every substring for uniqueness — O(n^2) or O(n^3). Too slow.

Hint 2

Use a sliding window with two pointers. The window contains only unique characters; you grow the right side and shrink the left side when a duplicate appears.

Hint 3

Map each character to its most-recently-seen index. When you encounter a repeat, jump the left pointer to one position past the prior occurrence (but only if that's further right than where left already is).

Solution approach

Reveal approach

Sliding window with a hash map of character -> last seen index. Walk the string with a right pointer; keep a left pointer at the start of the current window. For each character at right: if it was already seen and its last index is >= left, jump left to (lastSeen + 1) to evict it from the window. Otherwise the window is still all-unique. Update map[char] = right. The candidate max length each step is right - left + 1; track the global max. One pass, O(n) time, O(k) space where k is the alphabet size.

Complexity

Time
O(n)
Space
O(min(n, k))

Related patterns

  • sliding-window
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft
  • Bloomberg
  • Apple

Practice these live with InterviewChamp.AI

Drill Longest Substring Without Repeating Characters and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →