Longest Substring Without Repeating Characters
Receives a string of text and returns the length of the longest run of consecutive characters that contains no repetition. It uses the sliding-window technique: a window [start..i] is kept over the text so that it never holds a repeated character, while a map remembers the last index at which each character was seen. The right edge advances one character at a time; when that character was already seen inside the current window, the left edge jumps to just past that previous occurrence, discarding the repeat in a single move instead of stepping back one position at a time. After every move the window's length is compared against the best length seen so far. The whole text is scanned once, in O(n) time, using extra space proportional to the number of distinct characters. Comparison is exact and case-sensitive; spaces and punctuation count as ordinary characters. Returns the length (a number) of the longest repetition-free substring, and 0 for an empty text.
Visualization
- Input
- Result
Algorithm code
// Longest Substring Without Repeating Characters — a single pure function.
// Scans the text once with a sliding window [start..i] that never holds a
// repeated character. A map remembers the last index where each character was
// seen; when the current character was already seen inside the window, the
// window's left edge jumps just past that previous occurrence. The longest
// window length observed during the scan is the answer. No side effects.
/**
* @param {string} s - the text to scan, e.g. "abcabcbb"
* @returns {number} length of the longest substring without repeating characters
*/
export function lengthOfLongestSubstring(s) {
const lastSeen = new Map();
let start = 0;
let longest = 0;
for (let i = 0; i < s.length; i += 1) {
const char = s[i];
const seenAt = lastSeen.get(char);
if (seenAt !== undefined && seenAt >= start) {
start = seenAt + 1;
}
lastSeen.set(char, i);
const length = i - start + 1;
if (length > longest) {
longest = length;
}
}
return longest;
}FUNCTION lengthOfLongestSubstring(s):
lastSeen ← empty map from character to index
start ← 0
longest ← 0
FOR i FROM 0 TO length(s) - 1:
char ← s[i]
seenAt ← lastSeen[char]
IF seenAt exists AND seenAt >= start:
start ← seenAt + 1
lastSeen[char] ← i
length ← i - start + 1
IF length > longest:
longest ← length
RETURN longest