Find the bug · Medium

Fix the Longest Substring Without Repeats

Medium Find the bug Most askedSeen at Amazon, Bloomberg, Microsoft

lengthOfLongestSubstring(s) returns the length of the longest substring of s with no repeated characters.

The sliding-window code below passes the classic examples but gives answers that are too large for some strings. Find the bug and fix it.

Example 1

Input: s = "abcabcbb"
Output: 3

Example 2

Input: s = "abba"
Output: 2
Explanation: The buggy version returns 3.

The buggy code

function lengthOfLongestSubstring(s) {
  const last = new Map(); // char -> last index
  let left = 0;
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (last.has(s[i])) left = last.get(s[i]) + 1;
    last.set(s[i], i);
    best = Math.max(best, i - left + 1);
  }
  return best;
}

function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>(); // char -> last index
  let left = 0;
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (last.has(s[i])) left = last.get(s[i])! + 1;
    last.set(s[i], i);
    best = Math.max(best, i - left + 1);
  }
  return best;
}

def length_of_longest_substring(s: str) -> int:
    last: dict[str, int] = {}  # char -> last index
    left = best = 0
    for i, c in enumerate(s):
        if c in last:
            left = last[c] + 1
        last[c] = i
        best = max(best, i - left + 1)
    return best

<?php

function lengthOfLongestSubstring(string $s): int
{
    $last = []; // char => last index
    $left = 0;
    $best = 0;
    $n = strlen($s);
    for ($i = 0; $i < $n; $i++) {
        if (isset($last[$s[$i]])) {
            $left = $last[$s[$i]] + 1;
        }
        $last[$s[$i]] = $i;
        $best = max($best, $i - $left + 1);
    }
    return $best;
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>(); // char -> last index
        int left = 0, best = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (last.containsKey(c)) left = last.get(c) + 1;
            last.put(c, i);
            best = Math.max(best, i - left + 1);
        }
        return best;
    }
}

Hints

Hint 1

Trace "abba". Where is left when you reach the final a?

Hint 2

The window's left edge should only ever move to the right.

Find and fix the bug

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the bug and the fix

Time O(n) · Space O(alphabet)

The bug: when a repeated character is found, left jumps to the index after its last occurrence, even when that occurrence is already outside the window (to the left of left). In "abba", the final a was last seen at index 0, so left jumps back from 2 to 1 and the window "bba" is wrongly counted as valid.

The fix: never move left backwards: left = max(left, last[c] + 1).

Fixed version

function lengthOfLongestSubstring(s) {
  const last = new Map(); // char -> last index
  let left = 0;
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (last.has(s[i])) left = Math.max(left, last.get(s[i]) + 1); // never move left backwards
    last.set(s[i], i);
    best = Math.max(best, i - left + 1);
  }
  return best;
}

function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>(); // char -> last index
  let left = 0;
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (last.has(s[i])) left = Math.max(left, last.get(s[i])! + 1); // never move left backwards
    last.set(s[i], i);
    best = Math.max(best, i - left + 1);
  }
  return best;
}

def length_of_longest_substring(s: str) -> int:
    last: dict[str, int] = {}  # char -> last index
    left = best = 0
    for i, c in enumerate(s):
        if c in last:
            left = max(left, last[c] + 1)  # never move left backwards
        last[c] = i
        best = max(best, i - left + 1)
    return best

<?php

function lengthOfLongestSubstring(string $s): int
{
    $last = []; // char => last index
    $left = 0;
    $best = 0;
    $n = strlen($s);
    for ($i = 0; $i < $n; $i++) {
        if (isset($last[$s[$i]])) {
            $left = max($left, $last[$s[$i]] + 1); // never move left backwards
        }
        $last[$s[$i]] = $i;
        $best = max($best, $i - $left + 1);
    }
    return $best;
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>(); // char -> last index
        int left = 0, best = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (last.containsKey(c)) left = Math.max(left, last.get(c) + 1); // never move left backwards
            last.put(c, i);
            best = Math.max(best, i - left + 1);
        }
        return best;
    }
}

Common mistakes

Deleting old characters from the map instead: works but is easy to get wrong.
Updating best before moving left.