Need help understanding this longest substr algorithm Javascript

function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;

  for (let i = 0; i < str.length; i++) {
    let char = str[i];

    if (seen[char]) {
      console.log(start, seen[char])

      start = Math.max(start, seen[char]);
    }

    // index - beginning of substring + 1 (to include current in count)
    longest = Math.max(longest, i - start + 1);
    // store the index of the next char so as to not double count
    seen[char] = i + 1;
  }
  return longest;
}

console.log(findLongestSubstring("thisishowwedoit"))

Why are they using the line:

start = Math.max(start, seen[char]);

Wouldn’t I want the max of the start not the seen[char]? I’m confused on how this algorithm works.

Answer

• start stands for where we start counting length of current (unique letters) substring.
• seen[char] stands for last position of a char you encounter.

So there you are counting length of string having unique chars suddenly you hit something that seen before. If it was seen way way back, it might not be relevant because you are starting to count from position start. In that case Math.max(start)==start and you keep counting.

However you might have hit a char later than when you start counting. That’s a no-no and you need to start over, from that position (not before because you’d fail again) hoping to find a longer match. So that’s why Math.max(start, seen[char]).

It is not a good programming because it is confusing. An if statement would have been more illustrative as I hope was my explanation.

function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;

  for (let i = 0; i < str.length; i++) {
    let char = str[i];

    if (seen[char]) {
      console.log(start, seen[char], char)
      start = Math.max(start, seen[char]);
    }

    longest = Math.max(longest, i - start + 1);
    seen[char] = i + 1;
  }
  return longest;
}

console.log(findLongestSubstring("thisishowwedoit"))

.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}