Longest Substring Without Repeating Characters

Meta

String

Sliding Window

Hash Table

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

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Solution Walkthrough

This is the classic sliding window pattern combined with a hash map for O(1) duplicate checks. The window represents the current substring under consideration; it only ever grows from the right and shrinks from the left, never resetting from scratch.

Use a hash map to record the most recent index at which each character was seen.
Keep a left pointer marking the start of the current window (initially 0), and track the best length seen so far.
Move a right pointer across the string. For each character:
- If it was seen before and that occurrence is inside the current window (its stored index is >= left), jump left to just past that occurrence — this removes the duplicate from the window.
- Update the character's stored index to the current right.
- Update the best length using the current window size right - left + 1.

Because left only ever moves forward, each character is visited a bounded number of times, giving O(n) time complexity. Space complexity is O(min(n, charset size)) for the hash map.

function lengthOfLongestSubstring(s) {
    const lastSeen = new Map();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        const char = s[right];

        if (lastSeen.has(char) && lastSeen.get(char) >= left) {
            // Duplicate found inside the current window — shrink from the left
            left = lastSeen.get(char) + 1;
        }

        lastSeen.set(char, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

Related Algorithms

Hashing →