LeetCode #3 – Longest Substring Without Repeating Characters

Problem Statement

Task

Given a string s, find the length of the longest substring without repeating characters.
A substring here means a contiguous block of characters in s.

Examples:
- s = "abcabcbb" ⇒ answer is 3 (substring: "abc").
- s = "bbbbb" ⇒ answer is 1 (substring: "b").
- s = "pwwkew" ⇒ answer is 3 (substring: "wke").

Sliding Window with a Set (O(n))

High-Level Idea

We want the longest window [l, r] such that all characters in s[l..r] are distinct.
Use a Set to track all characters currently in the window.
We maintain:
- l: left pointer (start of current window).
- r: right pointer (current character we are adding).
While expanding r, if we see a character already in the set, we shrink from the left (l++) until that character is removed.
At each step, we update the answer with the current window size r - l + 1.

Core Logic (TypeScript)

function lengthOfLongestSubstring(s: string): number {
    const memo = new Set<string>();  // current window's characters

    let ans = 0;
    let l = 0;                        // left pointer

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

        // If c is already in the window, shrink from the left
        if (memo.has(c)) {
            while (s[l] !== c) {
                memo.delete(s[l]);
                l++;
            }
            memo.delete(s[l]);  // remove the previous occurrence of c
            l++;
        }

        memo.add(c);                   // extend window with s[r]

        // Update the best length so far
        if (r - l + 1 > ans) {
            ans = r - l + 1;
        }
    }

    return ans;
};

const solution1 = lengthOfLongestSubstring;

export {};

memo always contains exactly the set of characters in the current window s[l..r].
If the new character c is already in memo, the inner while loop shrinks the window from the left until the previous c is removed.
The window is always valid (no duplicates) when we reach the point where we update ans.

Example Walkthrough

Take s = "pwwkew".

Step (r index)	Character	l (left)	Window s[l..r]	Set contents	ans	Operation
r = 0	`'p'`	0	`"p"`	{ p }	1	Add 'p', update ans = 1
r = 1	`'w'`	0	`"pw"`	{ p, w }	2	Add 'w', update ans = 2
r = 2	`'w'`	1	`"ww"` → `"w"`	{ w }	2	Duplicate 'w': move l forward, remove 'p', then old 'w'
r = 3	`'k'`	2	`"wk"`	{ w, k }	2	Add 'k', ans stays 2
r = 4	`'e'`	2	`"wke"`	{ w, k, e }	3	Add 'e', update ans = 3
r = 5	`'w'`	3	`"kew"`	{ k, e, w }	3	Duplicate 'w': shrink until previous 'w' removed, final window "kew"

The longest valid window length we saw was 3 (substrings "wke" or "kew").

Why This Is O(n)

Each character is:
- Added to the set at most once.
- Removed from the set at most once.
The left pointer l and right pointer r both move from 0 to s.length - 1 without ever going backwards.
Therefore, the total number of operations is linear in the length of the string.

Time: O(n), where n = s.length.
Space: O(min(n, Σ)), where Σ is the character set (we at most store each distinct character in the current window).