Longest Substring that contains no repeated Characters Algorithm

Given a string, find the length of the longest substring with no repeated characters.

Input: "nnNfdfdf"
Output: 4 (the substring "Nfdf")

The intuition

Use a sliding window. Two pointers — left and right — define a window of unique characters. Expand the window by moving right. When you hit a duplicate, shrink from left until the duplicate is gone.

A Set tracks which characters are currently in the window. This gives you O(1) lookups for duplicates.

The code

const lengthOfLongestSubstring = (s) => {
    let left = 0;
    let maxLength = 0;
    const seen = new Set();

    for (let right = 0; right < s.length; right++) {
        while (seen.has(s[right])) {
            seen.delete(s[left]);
            left++;
        }
        seen.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};

Complexity

• Time: O(n) — each character is added and removed from the set at most once.
• Space: O(min(n, m)) — where m is the size of the character set (26 for lowercase letters, 128 for ASCII).

Trade-offs

The sliding window approach is optimal for this problem. You could use a Map instead of a Set to store the last index of each character, which lets you jump left directly to the right position instead of incrementing one by one. Slightly faster in practice, slightly harder to read.