3. Longest Substring Without Repeating Characters
mediumFind the length of the longest substring containing no repeated characters. The canonical sliding-window-with-hash-map problem and a common interview opener.
By Sam K., 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^4s consists of English letters, digits, symbols and spaces.
Examples
Example 1
s = "abcabcbb"3Explanation: The answer is "abc", with length 3.
Example 2
s = "bbbbb"1Explanation: The answer is "b", with length 1.
Example 3
s = "pwwkew"3Explanation: 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.
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
- Microsoft
- Bloomberg
- Apple
More Strings practice problems
- 5. Longest Palindromic Substring
- 6. Zigzag Conversion
- 14. Longest Common Prefix
- 20. Valid Parentheses
- 28. Find the Index of the First Occurrence in a String
- 49. Group Anagrams
- 58. Length of Last Word
- 76. Minimum Window Substring