Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters 🔗

Date: Jun 03, 2024

Tags: sliding-window

Description

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

Example 1:

          Input: s = "abcabcbb"
          Output: 3
          Explanation: The answer is "abc", with the length of 3.

Example 2:

          Input: s = "bbbbb"
          Output: 1
          Explanation: The answer is "b", with the length of 1.

Example 3:

          Input: s = "pwwkew"
          Output: 3
          Explanation: The answer is "wke", with the length of 3.
          Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 10⁴
s consists of English letters, digits, symbols and spaces.

Optimal

function lengthOfLongestSubstring(s: string): number {
  let l = 0;
  let r = 0;
  const result = new Set();
  let len = 0;

  while (r < s.length) {
    if (!result.has(s[r])) {
      result.add(s[r]);
      len = Math.max(len, r - l + 1);
      r++;
    } else {
      result.delete(result.values().next().value);
      l++;
    }
  }

  return len;
}

export { lengthOfLongestSubstring };