codejump
MediumPythonJavaScriptTypeScript

Sliding Window — Longest Substring Without Repeats

AlgorithmsSliding WindowStringsHash Table

Return the length of the longest substring of s in which no character
appears twice.

A variable-size window: grow it on the right one character at a time, and when
the new character is already inside the window, move the left edge **just past
its previous occurrence**. Remembering the last index of every character makes
that jump O(1), so the whole scan is O(n).

Examples

solve('abcabcbb')  → 3   // 'abc'
solve('bbbbb')     → 1   // 'b'
solve('pwwkew')    → 3   // 'wke' ('pwke' is not a substring)

Constraints

  • 0 <= s.length <= 50000
  • s holds letters, digits, symbols and spaces; every character counts, the

space included.

Sample tests

Test #1The classic example
Input: ["abcabcbb"]
Output: 3
Test #2One repeated character
Input: ["bbbbb"]
Output: 1
Test #3A substring, not a subsequence
Input: ["pwwkew"]
Output: 3