Topic: Learning notes
LeetCode 3: Longest Substring Without Repeating Characters in TypeScript
Keep an initial reset-and-rescan attempt, explain its O(n²) limit, then use a one-pass Map sliding window.
I started with two pointers and a Map. The first version resets the window after a duplicate and scans earlier characters again. It returns the right length, but the right pointer can move backward. The second version only moves the right pointer forward, which gives the O(n) solution this problem needs.
Problem
Original problem: LeetCode 3: Longest Substring Without Repeating Characters
Given a string s, return the length of its longest contiguous substring without repeated characters. The substring must be contiguous, so "pwke" is not a valid answer for "pwwkew".
Brute force
Start at every position and extend right until a duplicate appears. A fresh Set for each start makes the worst-case time O(n²) and auxiliary space O(n).
function lengthOfLongestSubstringBruteForce(s: string): number {
let longest = 0;
for (let start = 0; start < s.length; start += 1) {
const seen = new Set<string>();
for (let end = start; end < s.length; end += 1) {
if (seen.has(s[end])) break;
seen.add(s[end]);
longest = Math.max(longest, end - start + 1);
}
}
return longest;
}My first reset-and-rescan approach
The first version handles empty and one-character strings up front. It uses p1 and p2 for the window bounds, then stores each character’s last index in a Map. This keeps the original control flow and adds only the Map types.
function lengthOfLongestSubstring(s: string): number {
if (s.length === 0) return 0;
if (s.length === 1) return 1;
let res = 1;
const map = new Map<string, number>();
let p1 = 0;
let p2 = 1;
map.set(s[p1], p1);
while (p2 < s.length) {
if (map.has(s[p2])) {
p1 = map.get(s[p2])! + 1;
p2 = p1 + 1;
res = Math.max(map.size, res);
map.clear();
map.set(s[p1], p1);
} else {
map.set(s[p2], p2);
res = Math.max(map.size, res);
p2 += 1;
}
}
return res;
}This is not O(n log n) because it does not sort. The issue is that a duplicate sets p2 back to p1 + 1, so the code scans characters it already visited.
For a long unique prefix followed by the same sequence again, each duplicate can restart a long scan. The worst case is O(n²). The Map can also hold every distinct character in the active window, so its auxiliary space is O(n), not O(1).
My improved Map sliding window
The improved version stores each character’s latest index. The right pointer advances one position per iteration. The code does not clear the map or move right backward. If the character’s last index remains inside the current window, the left pointer jumps past it.
function lengthOfLongestSubstring(s: string): number {
const lastSeen = new Map<string, number>();
let left = 0;
let longest = 0;
for (let right = 0; right < s.length; right += 1) {
const char = s[right];
const previous = lastSeen.get(char);
if (previous !== undefined && previous >= left) {
left = previous + 1;
}
lastSeen.set(char, right);
longest = Math.max(longest, right - left + 1);
}
return longest;
}Empty input needs no special case. The loop does not run, so the initial 0 is the result. A one-character input naturally produces 1.
The map retains indexes that are left of the current window. That is why previous >= left matters. Without it, a string such as "abba" could move left backward and let a duplicate back into the window.
Why the sliding window is correct
At the start of each iteration, s[left..right - 1] contains no duplicates, and lastSeen stores the most recent index for each character.
After reading s[right], its previous occurrence either lies outside the window or it does not. In the second case, moving left to the next index removes the only conflict. Updating lastSeen leaves s[left..right] duplicate-free, so right - left + 1 is a valid candidate for the longest length.
The right pointer takes exactly n steps, and the left pointer only moves right. Interview analysis normally treats Map lookups and updates as average O(1), so total time is O(n). The map stores at most one entry per distinct character, which is O(min(n, c)) auxiliary space and usually written as O(n). Here, c is the number of possible distinct characters.
Fixed ASCII array version
If input is guaranteed to be 7-bit ASCII, a fixed 128-slot array can store last-seen positions. It does not improve the asymptotic time, which remains O(n), but it avoids Map hashing and dynamic allocation. The fixed array uses O(1) auxiliary space.
This is not a general replacement for Map in JavaScript strings. charCodeAt() reads UTF-16 code units. For non-ASCII text, keep the Map version or first decide whether the requirement counts code units or Unicode code points.
function lengthOfLongestSubstringAscii(s: string): number {
const lastSeen = new Int32Array(128).fill(-1);
let left = 0;
let longest = 0;
for (let right = 0; right < s.length; right += 1) {
const code = s.charCodeAt(right);
if (code >= lastSeen.length) {
throw new RangeError("This implementation only accepts ASCII input.");
}
left = Math.max(left, lastSeen[code] + 1);
lastSeen[code] = right;
longest = Math.max(longest, right - left + 1);
}
return longest;
}Minimal verification
import assert from "node:assert/strict";
assert.equal(lengthOfLongestSubstring("abcabcbb"), 3);
assert.equal(lengthOfLongestSubstring("bbbbb"), 1);
assert.equal(lengthOfLongestSubstring("pwwkew"), 3);
assert.equal(lengthOfLongestSubstring("abba"), 2);
assert.equal(lengthOfLongestSubstring("tmmzuxt"), 5);
assert.equal(lengthOfLongestSubstring(""), 0);
assert.equal(lengthOfLongestSubstringAscii("a b!a"), 4);Common mistakes
- Moving the left pointer whenever the map has the character. The last index may already be outside the window, so compare
previous >= left. - Clearing the map when a duplicate appears. It loses reusable indexes and makes the right pointer rescan.
- Calling map storage
O(1). It can storenentries unless the character set is fixed, such as a 128-slot ASCII array. - Treating a subsequence as a substring. This problem accepts only contiguous text.
- Applying the ASCII array to arbitrary Unicode text. Confirm the character range and counting unit first.
Transferable idea
The window condition is “no repeated characters.” When adding a character on the right breaks it, move the left side only far enough to remove that conflict. There is no need to rebuild the whole window. This is the core variable-length sliding-window pattern.