maw.sh > Mahmoud Ashraf Website

SupportPalestine

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 * 104
  • 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 };