Longest Substring Without Repeating Characters

string • sliding-window • hash-table
Medium
O(n)O(n)

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

Examples

Input
"abcabcbb"
Output
3
The answer is "abc" with length 3.
Input
"bbbbb"
Output
1
The answer is "b" with length 1.
Input
"pwwkew"
Output
3
The answer is "wke" with length 3.

Solution

Use a sliding window with two pointers (left, right). Move `right` forward and track the last index of each character in a map.
If a repeated character is seen and its last index is >= left, advance `left` to lastIndex + 1 to shrink the window.
Maintain the window length (right - left + 1) and update the maximum.
Time complexity is O(n)O(n) since each character is visited at most twice; space is O(min(n,m))O(min(n, m)) where m is alphabet size.

Code Solution

longest-substring.ts
ts
1
function lengthOfLongestSubstring(s: string): number {
2
  const last = new Map<string, number>();
3
  let left = 0;
4
  let best = 0;
5
  for (let right = 0; right < s.length; right++) {
6
    const ch = s[right];
7
    if (last.has(ch) && last.get(ch)! >= left) {
8
      left = last.get(ch)! + 1;
9
    }
10
    last.set(ch, right);
11
    best = Math.max(best, right - left + 1);
12
  }
13
  return best;
14
}