Longest Substring Without Repeating Characters

Loading...LeetCode

Problem

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.

Pseudocode

- iterate through string to add into a Set, using two pointers
    - one to iterate through loop
    - one as a trailing pointer to delete all letters in the set when repeated letters are found
- if letter found to be repeating/not unique
    - delete trailing letters using a second pointer in a while loop
    - increment pointer until all letters are deleted
    - repeated letter is added into set in the following sequence
- if letter is unique
    - add into set
    - set size = longest unique substring
    - use Math.max() to book keep

Solution

// https://leetcode.com/problems/longest-substring-without-repeating-characters/
var lengthOfLongestSubstring = function (s) {
  let maxLength = 0;
  let set = new Set();
  let left = 0;

  for (let i = 0; i < s.length; i++) {
    let curr = s[i];

    while (set.has(curr)) {
      set.delete(s[left]);
      left++;
    }

    set.add(curr);
    maxLength = Math.max(maxLength, set.size);
  }

  return maxLength;
};

Time and Space Complexity

Time

• What did the code do

• Total -

Space

• What did the code do

• Total -