Longest Substring Without Repeating Characters — LC 3 at Meta and Amazon

Problem Statement#

Given a string s, find the length of the longest substring without repeating characters.

Constraints:

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

Input:  s = "abcabcbb"
Output: 3

Input:  s = "pwwkew"
Output: 3

Why This Problem Matters#

LeetCode 3 Longest Substring Without Repeating Characters is a top-five most asked question at Meta, Amazon, and Microsoft. It is the canonical variable sliding window problem with a hash map, and interviewers explicitly use it to filter candidates who can apply the variable-window template fluently.

The brute force enumerates O(n^2) substrings and checks each for uniqueness, costing O(n^3). The sliding window with a hash map runs in O(n) time with O(min(n, m)) space where m is the alphabet size, and that is the expected answer at every FAANG level.

The pattern reappears in LC 159 Longest Substring with at Most Two Distinct Characters, LC 340 Longest Substring with at Most K Distinct Characters, LC 76 Minimum Window Substring, and LC 904 Fruit Into Baskets. Master this template and the entire family becomes mechanical.

The Core Insight#

The window invariant is "all characters inside the window are distinct." Expand the right edge by adding the new character to a hash map of last-seen positions. If the new character is already in the map and its previous index is inside the current window, jump the left edge to one past that previous index.

We do not shrink character by character. Jumping left directly to last_seen[ch] + 1 is correct because every position skipped over still violated the invariant or matched a position already excluded. This is the optimization over the slower "while shrink" version.

At every step the window is a valid candidate, so we update the answer with right - left + 1.

Visual Dry Run#

For s = "abcabcbb":

Solution (Optimal)#

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = 0
        best = 0
        for right, ch in enumerate(s):
            if ch in last_seen and last_seen[ch] >= left:
                left = last_seen[ch] + 1
            last_seen[ch] = right
            best = max(best, right - left + 1)
        return best

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

Time: O(n) — single pass with hash map updates Space: O(min(n, m)) — m is the alphabet size

Common Mistakes#

• Forgetting the guard last_seen[ch] >= left and jumping left backwards
• Using a set and shrinking one character at a time, which works but is slower than the jump
• Recomputing the substring length from scratch on each step, costing O(n^2)
• Returning the substring instead of its length
• Off-by-one: forgetting the + 1 in right - left + 1

Interview Tips#

• Lead with the brute force and immediately propose the variable sliding window improvement
• Explain why the jump is valid: "Every character at or before the previous occurrence of ch cannot extend a valid window past the duplicate, so jumping is safe"
• Walk through a string with a duplicate that occurred before left to show the guard in action
• Mention the alphabet-bounded space: for ASCII, the hash map has at most 128 entries

Follow-up Questions#

• What if at most k distinct characters are allowed? (Hint: LC 340, frequency map and shrink loop)
• What if exactly k distinct characters are required? (Hint: at-most-k minus at-most-(k-1))
• How would you return the actual substring? (Hint: track the start index of the best window)
• What if the input is a stream? (Hint: same template, hash map of last seen positions)
• How does this differ from LC 1695 Maximum Erasure Value? (Hint: replace length with sum)

Key Takeaways#

• LeetCode 3 Longest Substring Without Repeating Characters is a top-five FAANG question
• Use a variable sliding window with a hash map of last-seen indices
• Jump left to last_seen[ch] + 1 instead of shrinking one step at a time
• Always guard the jump with last_seen[ch] >= left to avoid moving backwards
• O(n) time and O(min(n, m)) space, where m is the alphabet size
• Pattern extends to LC 159, LC 340, LC 76, LC 904, and LC 1695
• Meta, Amazon, and Microsoft use this as a primary signal for sliding window fluency