Implement longestNonRepeatingSubstring(s). Given a string s, return the length (a number) of the longest contiguous substring of s that contains no duplicate characters. A substring is a contiguous slice of the original string — not a subsequence, which can skip characters. For "abcabcbb" the answer is 3 (the substring "abc"); for "bbbbb" it is 1 ("b"); for "pwwkew" it is 3 ("wke", not the 4-character subsequence "pwke").
This is the classic "longest substring without repeating characters" problem. The naive O(n²) solution is straightforward — and slow on long strings. The interesting work is doing it in O(n) with a sliding window plus a last-seen index map.
// s: string — any string (may be empty, may contain unicode)
// returns: number — length of the longest substring with no repeats
function longestNonRepeatingSubstring(s: string): number;longestNonRepeatingSubstring('abcabcbb'); // → 3 ("abc")
longestNonRepeatingSubstring('bbbbb'); // → 1 ("b")
longestNonRepeatingSubstring('pwwkew'); // → 3 ("wke", NOT "pwke" — subsequence)longestNonRepeatingSubstring(''); // → 0 (empty string)
longestNonRepeatingSubstring('z'); // → 1 (single char)
longestNonRepeatingSubstring('abcdef'); // → 6 (all unique → full length)longestNonRepeatingSubstring('a b a b'); // → 3 (space counts as a character; e.g. "b a")
longestNonRepeatingSubstring('abc123abc');// → 6 ("abc123")number. If you also want the substring itself, that's an extension — see Going further in the solution.s. "pwke" is a valid subsequence of "pwwkew" but not a substring; the correct substring answer is "wke" (length 3)."a b" has length 3 (a, space, b) and contains no duplicates.0, not undefined. A common bug is initialising max to undefined and short-circuiting on length 0.String.prototype mutators."🙂" made of surrogate pairs). The tests stick to BMP characters; if you want to handle astral plane characters, see Gotchas in the solution.You'll walk a window across the string from left to right; whenever a duplicate enters the window, you collapse the left side just enough to push the previous copy out.
You're scanning a string left-to-right, watching for the longest run of characters in which nothing repeats. The classic trap is mixing up substring (contiguous slice) with subsequence (any in-order pick). For "pwwkew" the correct substring answer is "wke" with length 3 — "pwke" is a valid subsequence but it skips the second w, so it doesn't count.
The brute-force version is the obvious one — try every starting index, expand until you hit a repeat, remember the max. The interesting version finishes in a single pass because each character is only ever visited twice — once when the right edge moves over it, and once when the left edge eventually catches up.
Picture two pointers, left and right, bracketing a window over the string. right marches forward one step at a time. Inside the bracket, every character is unique — that's the invariant we maintain. The window's width (right - left + 1) is a candidate answer; the largest width we ever see is the final return value.
The piece of state that makes this fast is a Map from character to its last seen index. When right lands on a character we've seen before, the map tells us exactly where the previous copy lives, so we can jump left past it in one step rather than scanning.
The straightforward approach: for every starting index i, expand a Set rightward until you find a duplicate; record the size; move on.
function longestNonRepeatingSubstringNaive(s) {
let max = 0;
for (let i = 0; i < s.length; i++) {
const seen = new Set();
for (let j = i; j < s.length; j++) {
if (seen.has(s[j])) break; // duplicate — stop expanding
seen.add(s[j]);
}
max = Math.max(max, seen.size);
}
return max;
}This is correct — it returns the right answer for every input. The problem is the cost. For each of n starting indices, the inner loop scans up to n more characters; that's O(n²) total. On "abcabcbb" (8 chars) it's fine — about 36 inner iterations. But on a 100,000-character string of mostly-unique runs, the brute force does roughly 10 billion operations and takes seconds to minutes. The deeper smell: every time the outer loop advances by one, the inner loop reruns work it already did at the previous i. That repeated work is the signal that a one-pass algorithm exists.
function longestNonRepeatingSubstring(s) {
// left edge of the current window. Everything in s[left..right]
// is guaranteed to be unique (that's our invariant).
let left = 0;
// largest window width we've ever seen. Starts at 0 so empty
// strings return 0, not undefined.
let max = 0;
// Map from character → the index where we LAST saw it.
// Using Map (not a plain object) keeps lookups O(1) and works
// for any character — including ones that would collide with
// Object.prototype keys like "constructor" or "__proto__".
const seen = new Map();
for (let right = 0; right < s.length; right++) {
const ch = s[right];
// The critical check: ch is a duplicate AND its previous copy
// is still INSIDE the current window. If the previous copy is
// at an index < left, it's already been pushed out by an
// earlier jump and doesn't count.
if (seen.has(ch) && seen.get(ch) >= left) {
// Jump left to one past the previous copy. That single
// assignment removes the duplicate AND every character
// before it from the window in O(1) — no scanning.
left = seen.get(ch) + 1;
}
// Always update the last-seen index, whether or not we jumped.
// Even if ch isn't in the window right now, we'll need its
// up-to-date position the NEXT time we see it.
seen.set(ch, right);
// Current window width is right - left + 1. Update max if
// this window is the widest so far.
max = Math.max(max, right - left + 1);
}
return max;
}
module.exports = { longestNonRepeatingSubstring };Three shifts from the naive version. First, we only loop once — right walks 0 to n-1, no nested loop. Second, the Map carries last-seen positions, so when we hit a duplicate we know where to jump left instead of scanning for it. Third, the >= left guard is what lets us safely keep stale entries in the map — an older duplicate that's already outside the window is irrelevant, so we ignore it instead of paying to clean it up.
Why a Map and not a plain object? Two reasons. Plain-object property access is O(1) on average but degrades on hostile keys, and certain keys like "__proto__" or "constructor" collide with Object.prototype. Map sidesteps both — every string key is just a string key, with consistent O(1) access.
Trace longestNonRepeatingSubstring("pwwkew") end-to-end. Initial state: left = 0, max = 0, seen = {}.
right=0, ch='p'. Not in seen. Set seen = {p: 0}. Width = 0 - 0 + 1 = 1. max = 1.
right=1, ch='w'. Not in seen. Set seen = {p: 0, w: 1}. Width = 1 - 0 + 1 = 2. max = 2.
right=2, ch='w'. Duplicate. seen.get('w') = 1, and 1 >= left (0) — it's in-window. Jump left = 1 + 1 = 2. Update seen = {p: 0, w: 2}. Width = 2 - 2 + 1 = 1. max stays at 2.
right=3, ch='k'. Not in seen. Set seen = {p: 0, w: 2, k: 3}. Width = 3 - 2 + 1 = 2. max stays at 2.
right=4, ch='e'. Not in seen. Set seen = {p: 0, w: 2, k: 3, e: 4}. Width = 4 - 2 + 1 = 3. max = 3.
right=5, ch='w'. Duplicate. seen.get('w') = 2, and 2 >= left (2) — still in-window. Jump left = 2 + 1 = 3. Update seen = {p: 0, w: 5, k: 3, e: 4}. Width = 5 - 3 + 1 = 3. max stays at 3.
Final return: 3. Notice that 'p' is sitting in the map at index 0 the whole time — perfectly harmless because we always check seen.get(ch) >= left before jumping. If we'd written just seen.has(ch), we would have wrongly jumped left past 'p' on a later character collision and broken the answer.
if (seen.has(ch)) alone is wrong — a character we saw long ago, already pushed out by an earlier jump, would rewind left backwards. Always check seen.get(ch) >= left so only in-window duplicates trigger a jump. Without this guard, "abba" returns 1 instead of 2.seen.set(ch, right), even on a no-jump iteration. If you only set on duplicates, you'll miss the very first occurrence of every character and seen.get(ch) will return undefined the next time, breaking the check. The pattern is: the map always reflects the latest index of every character we've encountered, period.0, not undefined. max must start at 0 so the loop-never-runs case still returns a number. Returning undefined is the single most common bug here — it usually passes the typeof check by accident if you don't test for it explicitly."pwwkew" → 3 not 4. If your answer is 4, you're computing the longest subsequence of distinct characters, which is just the count of unique characters. That's a different (easier) problem.s[i] on a string containing emoji like "🙂" returns a high or low surrogate — half a character. For BMP characters (Latin, accented Latin, most CJK) this is fine. To handle the full Unicode range correctly, iterate with for (const ch of s) and track the code-point position separately, or convert via Array.from(s) once up front. The tests here stick to BMP, but you should know the gap.bestLeft and bestLen separately, updating them only when you set a new max. At the end return s.slice(bestLeft, bestLeft + bestLen). Same O(n) cost.Map of in-window counts, shrink left whenever the map size exceeds K. Same O(n) shape.s arrives one character at a time (a network stream, a file read), the algorithm needs no changes — process each character on arrival, return max whenever asked. The Map grows with the alphabet, not the stream length.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Implement longestNonRepeatingSubstring(s). Given a string s, return the length (a number) of the longest contiguous substring of s that contains no duplicate characters. A substring is a contiguous slice of the original string — not a subsequence, which can skip characters. For "abcabcbb" the answer is 3 (the substring "abc"); for "bbbbb" it is 1 ("b"); for "pwwkew" it is 3 ("wke", not the 4-character subsequence "pwke").
This is the classic "longest substring without repeating characters" problem. The naive O(n²) solution is straightforward — and slow on long strings. The interesting work is doing it in O(n) with a sliding window plus a last-seen index map.
// s: string — any string (may be empty, may contain unicode)
// returns: number — length of the longest substring with no repeats
function longestNonRepeatingSubstring(s: string): number;longestNonRepeatingSubstring('abcabcbb'); // → 3 ("abc")
longestNonRepeatingSubstring('bbbbb'); // → 1 ("b")
longestNonRepeatingSubstring('pwwkew'); // → 3 ("wke", NOT "pwke" — subsequence)longestNonRepeatingSubstring(''); // → 0 (empty string)
longestNonRepeatingSubstring('z'); // → 1 (single char)
longestNonRepeatingSubstring('abcdef'); // → 6 (all unique → full length)longestNonRepeatingSubstring('a b a b'); // → 3 (space counts as a character; e.g. "b a")
longestNonRepeatingSubstring('abc123abc');// → 6 ("abc123")number. If you also want the substring itself, that's an extension — see Going further in the solution.s. "pwke" is a valid subsequence of "pwwkew" but not a substring; the correct substring answer is "wke" (length 3)."a b" has length 3 (a, space, b) and contains no duplicates.0, not undefined. A common bug is initialising max to undefined and short-circuiting on length 0.String.prototype mutators."🙂" made of surrogate pairs). The tests stick to BMP characters; if you want to handle astral plane characters, see Gotchas in the solution.You'll walk a window across the string from left to right; whenever a duplicate enters the window, you collapse the left side just enough to push the previous copy out.
You're scanning a string left-to-right, watching for the longest run of characters in which nothing repeats. The classic trap is mixing up substring (contiguous slice) with subsequence (any in-order pick). For "pwwkew" the correct substring answer is "wke" with length 3 — "pwke" is a valid subsequence but it skips the second w, so it doesn't count.
The brute-force version is the obvious one — try every starting index, expand until you hit a repeat, remember the max. The interesting version finishes in a single pass because each character is only ever visited twice — once when the right edge moves over it, and once when the left edge eventually catches up.
Picture two pointers, left and right, bracketing a window over the string. right marches forward one step at a time. Inside the bracket, every character is unique — that's the invariant we maintain. The window's width (right - left + 1) is a candidate answer; the largest width we ever see is the final return value.
The piece of state that makes this fast is a Map from character to its last seen index. When right lands on a character we've seen before, the map tells us exactly where the previous copy lives, so we can jump left past it in one step rather than scanning.
The straightforward approach: for every starting index i, expand a Set rightward until you find a duplicate; record the size; move on.
function longestNonRepeatingSubstringNaive(s) {
let max = 0;
for (let i = 0; i < s.length; i++) {
const seen = new Set();
for (let j = i; j < s.length; j++) {
if (seen.has(s[j])) break; // duplicate — stop expanding
seen.add(s[j]);
}
max = Math.max(max, seen.size);
}
return max;
}This is correct — it returns the right answer for every input. The problem is the cost. For each of n starting indices, the inner loop scans up to n more characters; that's O(n²) total. On "abcabcbb" (8 chars) it's fine — about 36 inner iterations. But on a 100,000-character string of mostly-unique runs, the brute force does roughly 10 billion operations and takes seconds to minutes. The deeper smell: every time the outer loop advances by one, the inner loop reruns work it already did at the previous i. That repeated work is the signal that a one-pass algorithm exists.
function longestNonRepeatingSubstring(s) {
// left edge of the current window. Everything in s[left..right]
// is guaranteed to be unique (that's our invariant).
let left = 0;
// largest window width we've ever seen. Starts at 0 so empty
// strings return 0, not undefined.
let max = 0;
// Map from character → the index where we LAST saw it.
// Using Map (not a plain object) keeps lookups O(1) and works
// for any character — including ones that would collide with
// Object.prototype keys like "constructor" or "__proto__".
const seen = new Map();
for (let right = 0; right < s.length; right++) {
const ch = s[right];
// The critical check: ch is a duplicate AND its previous copy
// is still INSIDE the current window. If the previous copy is
// at an index < left, it's already been pushed out by an
// earlier jump and doesn't count.
if (seen.has(ch) && seen.get(ch) >= left) {
// Jump left to one past the previous copy. That single
// assignment removes the duplicate AND every character
// before it from the window in O(1) — no scanning.
left = seen.get(ch) + 1;
}
// Always update the last-seen index, whether or not we jumped.
// Even if ch isn't in the window right now, we'll need its
// up-to-date position the NEXT time we see it.
seen.set(ch, right);
// Current window width is right - left + 1. Update max if
// this window is the widest so far.
max = Math.max(max, right - left + 1);
}
return max;
}
module.exports = { longestNonRepeatingSubstring };Three shifts from the naive version. First, we only loop once — right walks 0 to n-1, no nested loop. Second, the Map carries last-seen positions, so when we hit a duplicate we know where to jump left instead of scanning for it. Third, the >= left guard is what lets us safely keep stale entries in the map — an older duplicate that's already outside the window is irrelevant, so we ignore it instead of paying to clean it up.
Why a Map and not a plain object? Two reasons. Plain-object property access is O(1) on average but degrades on hostile keys, and certain keys like "__proto__" or "constructor" collide with Object.prototype. Map sidesteps both — every string key is just a string key, with consistent O(1) access.
Trace longestNonRepeatingSubstring("pwwkew") end-to-end. Initial state: left = 0, max = 0, seen = {}.
right=0, ch='p'. Not in seen. Set seen = {p: 0}. Width = 0 - 0 + 1 = 1. max = 1.
right=1, ch='w'. Not in seen. Set seen = {p: 0, w: 1}. Width = 1 - 0 + 1 = 2. max = 2.
right=2, ch='w'. Duplicate. seen.get('w') = 1, and 1 >= left (0) — it's in-window. Jump left = 1 + 1 = 2. Update seen = {p: 0, w: 2}. Width = 2 - 2 + 1 = 1. max stays at 2.
right=3, ch='k'. Not in seen. Set seen = {p: 0, w: 2, k: 3}. Width = 3 - 2 + 1 = 2. max stays at 2.
right=4, ch='e'. Not in seen. Set seen = {p: 0, w: 2, k: 3, e: 4}. Width = 4 - 2 + 1 = 3. max = 3.
right=5, ch='w'. Duplicate. seen.get('w') = 2, and 2 >= left (2) — still in-window. Jump left = 2 + 1 = 3. Update seen = {p: 0, w: 5, k: 3, e: 4}. Width = 5 - 3 + 1 = 3. max stays at 3.
Final return: 3. Notice that 'p' is sitting in the map at index 0 the whole time — perfectly harmless because we always check seen.get(ch) >= left before jumping. If we'd written just seen.has(ch), we would have wrongly jumped left past 'p' on a later character collision and broken the answer.
if (seen.has(ch)) alone is wrong — a character we saw long ago, already pushed out by an earlier jump, would rewind left backwards. Always check seen.get(ch) >= left so only in-window duplicates trigger a jump. Without this guard, "abba" returns 1 instead of 2.seen.set(ch, right), even on a no-jump iteration. If you only set on duplicates, you'll miss the very first occurrence of every character and seen.get(ch) will return undefined the next time, breaking the check. The pattern is: the map always reflects the latest index of every character we've encountered, period.0, not undefined. max must start at 0 so the loop-never-runs case still returns a number. Returning undefined is the single most common bug here — it usually passes the typeof check by accident if you don't test for it explicitly."pwwkew" → 3 not 4. If your answer is 4, you're computing the longest subsequence of distinct characters, which is just the count of unique characters. That's a different (easier) problem.s[i] on a string containing emoji like "🙂" returns a high or low surrogate — half a character. For BMP characters (Latin, accented Latin, most CJK) this is fine. To handle the full Unicode range correctly, iterate with for (const ch of s) and track the code-point position separately, or convert via Array.from(s) once up front. The tests here stick to BMP, but you should know the gap.bestLeft and bestLen separately, updating them only when you set a new max. At the end return s.slice(bestLeft, bestLeft + bestLen). Same O(n) cost.Map of in-window counts, shrink left whenever the map size exceeds K. Same O(n) shape.s arrives one character at a time (a network stream, a file read), the algorithm needs no changes — process each character on arrival, return max whenever asked. The Map grows with the alphabet, not the stream length.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.