[leetcode] 3. Longest Substring Without Repeating Characters

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^4
• s consists of English letters, digits, symbols, and spaces.

Approach

The idea is to use a sliding window(indicated by the red dashed box) to keep track of the current substring(start as left pointer, i as right pointer). We also use a position map to store the last seen index of each character.

If the character has been seen and is within the current sliding window, we update the start pointer to the next index of the character. We also update the maximum length of the substring found.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  // Store the last seen index of each character
  let positionMap = {};
  // Marks the beginning of the current substring window
  let start = 0;
  // Keeps track of the longest substring found
  let maximumLength = 0;

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

    // If the character has been seen and is within the current window
    if (positionMap[c] >= start) {
      start = positionMap[c] + 1;
    }

    positionMap[c] = i;
    maximumLength = Math.max(maximumLength, i - start + 1);
  }

  return maximumLength;
};

Complexity Analysis

Time Complexity

The time complexity is O(2n) because, in the worst case, each character might be visited twice. This simplifies to O(n).

Space Complexity

The space complexity is O(min(n, m)) where n is the length of the string and m is the size of the character set. This is because we store the last seen index of each character. In the worst case, when all characters are unique, the space complexity is O(n).