Coding problem · Medium · Sliding Window

Longest Substring Without Repeating Characters

Medium Algorithms & data structures Most askedSeen at Amazon, Google, Meta, Microsoft, Bloomberg

Given a string s, return the length of the longest substring (contiguous) without repeating characters.

Example 1

Input: s = "abcabcbb"
Output: 3
Explanation: "abc"

Example 2

Input: s = "bbbbb"
Output: 1

Example 3

Input: s = "pwwkew"
Output: 3
Explanation: "wke" — "pwke" is a subsequence, not a substring.

Constraints

0 <= s.length <= 5·10^4

Hints

Hint 1

Grow a window to the right; when a character repeats, shrink from the left.

Hint 2

Store each character's last index so you can jump the left edge directly.

Write and run your solution

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

Solution and explanation

Show the solution

Time O(n) · Space O(min(n, alphabet))

Keep a window [left, right] with no repeats and a map of each character's last index. When s[right] was last seen inside the window, move left just past that position (never backwards — see "abba"). The answer is the largest window width.

Reference solution

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

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

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

<?php

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            Integer prev = last.get(s.charAt(right));
            if (prev != null && prev >= left) left = prev + 1;
            last.put(s.charAt(right), right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Common mistakes

Moving left backwards when the previous occurrence is before the window ("abba").

Best Time to Buy and Sell Stock · Easy
Minimum Window Substring · Hard