Longest Substring Without Repeating Characters

Given a string s, find the longest substring (a contiguous block of characters) in which no character occurs more than once, and return its length.

Characters are compared exactly: a and A are different, and spaces, digits and symbols count as characters too. A substring must be contiguous; picking scattered characters (a subsequence) does not count. The empty string has answer 0.

Example 1

Example 2

Example 3

Constraints

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

Pattern Path · Sliding Window · problem 52 of 169

Start simple

For every start index, extend to the right with a set until a character repeats, tracking the longest: O(n²) time (O(n·k) with alphabet size k).

The key idea

Maintain a sliding window s[left..right] that never contains a repeated character, and remember for each character the last index where it appeared.

Advance right one character at a time. If the new character c was last seen at an index inside the window (last[c] >= left), the window now holds two copies of c. Every window that still includes the earlier copy is invalid, so jump left straight to last[c] + 1. That is the smallest shift that restores the invariant, so no valid window is skipped.

The check last[c] >= left matters: a stale index from before the window must not drag left backward. The string "abba" shows why: at the final a, its old index 0 is already outside the window.

After each step, record the window length right - left + 1. Both pointers only move forward, so the scan is linear.

Complexity

• Time: O(n)
• Space: O(k), where k is the number of distinct characters

Python

class Solution:
    def lengthOfLongestSubstring(self, s):
        last = {}  # character -> most recent index
        left = best = 0
        for right, c in enumerate(s):
            if last.get(c, -1) >= left:
                left = last[c] + 1  # jump past the previous copy of c
            last[c] = right
            best = max(best, right - left + 1)
        return best

JavaScript

var lengthOfLongestSubstring = function(s) {
  const last = new Map(); // character -> most recent index
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (last.has(c) && last.get(c) >= left) {
      left = last.get(c) + 1; // jump past the previous copy of c
    }
    last.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
};

What the interviewer is checking

This is the canonical variable-size sliding window: the interviewer wants to see a clear invariant, a correct shrink rule, and linear time rather than re-scanning.

Mistakes to avoid

• Moving left backward to a stale index, e.g. on "abba".
• Resetting the window to start at right on a repeat, which skips valid windows (try "dvdf").
• Forgetting the empty string or a string of a single repeated character.
• Counting a subsequence instead of a contiguous substring.

Follow-ups to expect

• Return the substring itself, not just its length. (Record left when best improves.)
• Allow at most k distinct characters instead. (Shrink while distinct count exceeds k.)
• Allow each character at most twice. (Count map, shrink while any count exceeds 2.)

In real software

Sliding windows with a last-seen map power rate limiters, deduplication of recent events in streams, and finding the longest session without a repeated action in analytics.

Practice next