#3 - Longest Substring Without Repeating Characters

MediumArray / String

Given a string s, find the length of the longest substring without repeating characters.

Input	Output
s = "abcabcbb"	3 (substring "abc")
s = "bbbbb"	1 (substring "b")
s = "pwwkew"	3 (substring "wke")

Solution Space

Try it

/**
 * Returns the length of the longest substring with all unique characters.
 *
 * @param s Input string
 * @returns Length of the longest substring without repeating characters
 */
export function lengthOfLongestSubstring(s: string): number {
  // Maps each character to the index where it was last seen
  const lastSeen = new Map<string, number>();
  let maxLen = 0;
  let left = 0;

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

    if (lastSeen.has(ch)) {
      // Jump left past the previous occurrence (but never backwards)
      left = Math.max(left, lastSeen.get(ch)! + 1);
    }

    lastSeen.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

Approach: sliding window with hash-map – maintain a window of unique characters, expanding the right pointer and shrinking the left pointer when duplicates are found.

Time: O(n) – single pass; each character is visited once by `right`.

Space: O(min(n, m)) – where m is the character-set size (e.g. 128 for ASCII).

Alternative approaches:

Approach	Idea	Time	Space
Sliding window with Set	Expand right, shrink left (removing chars from Set) on duplicate.	O(n) worst-case (each char added/removed at most once)	O(min(n, m))
Brute force	Check every substring for uniqueness.	O(n³)	O(min(n, m))

Why the Map approach is preferred:

• When a duplicate is found, the left pointer jumps directly to the correct position instead of incrementing one-by-one, making the logic cleaner and consistently O(n).

#1 Two Sum

#15 3Sum