Sliding Window · 012Medium
Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring that contains no repeating characters.
Constraints
- 0 <= s.length <= 5 * 10^4
- s consists of English letters, digits, symbols and spaces.
Examples
lengthOfLongestSubstring("abcabcbb") -> 3 // "abc"
lengthOfLongestSubstring("bbbbb") -> 1 // "b"
lengthOfLongestSubstring("pwwkew") -> 3 // "wke", not "pwke"
lengthOfLongestSubstring("") -> 0 // empty string
lengthOfLongestSubstring(" ") -> 1 // a space is a character
lengthOfLongestSubstring("tmmzuxt") -> 5 // "mzuxt"; never move the left edge backwardsEdge cases
- Empty string returns 0.
- All characters identical.
- A substring is contiguous — a subsequence is not.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — check every substring for uniqueness.
- Target
- O(n) time, O(min(n, charset)) space — sliding window with a map of last-seen indices, jumping the left edge forward on a repeat.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/03-sliding-window/012-longest-substring-without-repeating-characters.js ./practice c 012