Longest substring without repeating characters

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

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

// Approach 1
// Calculate maxLen every time, and adjust start when already seen character is found.
const lengthOfLongestSubstring = function (s) {
  if (!s) return 0;

  let start = 0;
  let end = 0;
  let map = new Map();
  let res = 0;

  while (end < s.length) {
    let curChar = s[end];
    if (map.has(curChar)) {
      const seenIdx = map.get(curChar);
      // make sure you don't jump back to the wrong index.
      // ex: abba
      // when looking at the second 'a', don't jump back to
      // first 'b' (seenIdx + 1). This is wrong because
      // you are now considering two 'b's.
      // Instead, use the below condition.
      start = Math.max(seenIdx + 1, start);
    }

    map.set(curChar, end);
    // this +1 avoids one-off error.
    // ex: "a"
    // Both end and start will be zero, so according to
    // our logic if we don't do +1, 0 - 0 -> 0
    // This will give us a wrong answer.
    res = Math.max(res, end - start + 1);
    end++;
  }

  return res;
};

// Approach 2
// Calculate maxLen only when the existing character is found
const lengthOfLongestSubstring = function (s) {
  if (!s) return 0;

  let start = 0;
  let end = 0;
  let map = new Map();
  let res = 0;

  while (end < s.length) {
    let curChar = s[end];
    if (map.has(curChar) && map.get(curChar) >= start) {
      // Note: here we are first calculating the maxLen,
      // without considering this new 'already seen' character.
      // Basically we are considering(adding) the seen character when
      // calculating the maxLen, and then we increase the start idx.
      res = Math.max(res, end - start);
      start = map.get(curChar) + 1;
    }

    map.set(curChar, end);
    end++;
  }

  return Math.max(res, end - start);
};

There are two approaches:

1. Where you calculate maxLen every time. Adjust startIndex accordingly.
2. Where you calculate maxLen only when the existing character is found.

Check old and new solution to understand both approaches.

To avoid one-off error when calculating the maxLen, make sure you run the loop till endIdx < s.length. This will make sure when the loop ends, endIdx will be equal to s.length. Then you can substract the startIdx from endIdx to get the length.

Take an example:

s = "abcd"
At the beginning: len(s) = 4, startIdx = endIdx = 0
When the loop (endIdx < s.length) ends, endIdx = 4
Then, endIdx - startIdx = 4 - 0 = 4, which is the correct answer.

Edge cases:

s = ""
s = "a"
s = "abba". Here the first 'already seen' character is 'b', and the second 'already seen' character is 'a'. Note that 'a' comes before 'b' at the start of the given string. If you are not cautious when you set the 'startIdx', then you may jump back to the wrong startIdx, which will be idx(a) + 1. This is wrong because you are now again considering the first 'b'(idx = 1) when calculating the maxLen. The wrong answer will be 4 - 1 = 3, which accounts for two 'b's in it.