Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Longest Substring Without Repeating Characters

Find the length of the longest substring with no repeated character using a variable-size sliding window and a map, in O(n) time.

Updated Short read: 4 min read

Approaches at a glance

ApproachTimeSpace
Brute forceO(n²)O(k)
Sliding window with last-seen mapO(n)O(k)

The problem

Given a string, return the length of the longest substring in which no character appears twice. A substring is a run of consecutive characters.

"abcabcbb"   →  3    ("abc")
"bbbbb"      →  1    ("b")
"pwwkew"     →  3    ("wke")
""           →  0

In the third example "pwke" is not a valid answer: its characters are not consecutive in the original string.

In the complexity figures, n is the length of the string and k is the number of different characters in it.

Approach 1: brute force

From each starting position, extend to the right until a character repeats.

JavaScript

function lengthOfLongestSubstringBruteForce(text) {
  let best = 0;
  for (let start = 0; start < text.length; start++) {
    const seen = new Set();
    for (let end = start; end < text.length; end++) {
      if (seen.has(text[end])) break;
      seen.add(text[end]);
      best = Math.max(best, end - start + 1);
    }
  }
  return best;
}

Python

def length_of_longest_substring_brute_force(text):
    best = 0
    for start in range(len(text)):
        seen = set()
        for end in range(start, len(text)):
            if text[end] in seen:
                break
            seen.add(text[end])
            best = max(best, end - start + 1)
    return best

Time O(n²) in the worst case. Space O(k) for the set.

Approach 2: sliding window

The brute force throws away everything it learned each time it moves to a new start. A sliding window keeps it.

Hold a window from start to end that never contains a repeat. Move end one character at a time. If the new character is already inside the window, the window is no longer valid, and the fix is to move start to just past the earlier copy of that character.

To do that without searching, keep a map from each character to the index where it was last seen.

JavaScript

function lengthOfLongestSubstring(text) {
  const lastSeen = new Map();
  let start = 0;
  let best = 0;
 
  for (let end = 0; end < text.length; end++) {
    const ch = text[end];
 
    if (lastSeen.has(ch) && lastSeen.get(ch) >= start) {
      start = lastSeen.get(ch) + 1;
    }
 
    lastSeen.set(ch, end);
    best = Math.max(best, end - start + 1);
  }
  return best;
}

Python

def length_of_longest_substring(text):
    last_seen = {}
    start = 0
    best = 0
 
    for end, ch in enumerate(text):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
 
        last_seen[ch] = end
        best = max(best, end - start + 1)
    return best

Walkthrough

"abba":

end Character Last seen at Action Window best
0 a never Extend "a" 1
1 b never Extend "ab" 2
2 b 1, inside the window start = 2 "b" 2
3 a 0, before the window Extend "ba" 2

Time O(n): one pass, with constant-time map operations. Space O(k).

Why the check includes >= start

The map remembers every character ever seen, including ones the window has already moved past. In the last row above, a was last seen at index 0, but the window starts at index 2, so that old a is no longer in it and is not a repeat.

Without the >= start condition, the code would set start back to 1. The window would then be "bba", which contains a repeat, and the function would return 3 instead of 2. start must never move backwards.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(lengthOfLongestSubstring("abcabcbb")); // 3
console.log(lengthOfLongestSubstring("abba")); // 2

Python

print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("abba"))  # 2

The comment after each line is the result you should see.

Common mistakes

  • Leaving out the >= start check. "abba" is the standard test for this bug.
  • Getting the window length wrong. It is end - start + 1, because both ends are included.
  • Updating best only when a repeat is found. The longest window may be the one that reaches the end of the string, so update on every step.

Original problem: LeetCode 3: Longest Substring Without Repeating Characters