Longest substring without repeating characters

Medium TimeO(n) SpaceO(1)

Given a string s, return the length of the longest stretch of adjacent characters within it that holds no character twice. The characters have to be contiguous, so this is a substring rather than a subsequence, and no character may appear twice inside it. An empty string has an answer of 0, and the answer is the length rather than the stretch itself.

Examples

Example 1

Input
s = "abcabcbb"
Output
3
"abc", "bca" and "cab" are each 3 long; the trailing "bb" cannot beat them.

Example 2

Input
s = "bbbbb"
Output
1
Every character repeats the one before it, so no stretch is ever wider than a single b.

The Code

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map();
  let best = 0;
  let start = 0;
  for (let end = 0; end < s.length; end++) {
    const ch = s[end];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= start) {
      start = lastSeen.get(ch) + 1;
    }
    lastSeen.set(ch, end);
    const width = end - start + 1;
    if (width > best) best = width;
  }
  return best;
}
lengthOfLongestSubstring("abcabcbb");
Done
Step through lengthOfLongestSubstring("abcabcbb") call by call

More like this

All strings examples (13) →