Brute Forcing It

This is one of those problems which is deceptively challenging. When you're given the prompt, it sounds like an easy iteration problem-- but we'll need to have it perform at a decent complexity.

Before even considering optimization, though, let's consider the most straightforward solution possible. So we want to know the longest substring with no duplicate characters. How would we do this manually, given the word algodaily? To achieve this, why not just look at every single substring?

Here's how the steps would go:

1. First, we consider a. Longest max is 1.
2. Then, we look at al. Longest max is now 2.
3. We look at alg. It's now 3.
4. o - 4
5. d - 5
6. a - wait, we've seen this before. Max is still 5, and the next few steps are also invalid and won't change the max.
7. We have substring algodai - i - substring has duplicate, so invalld
8. algodail - l - substring has duplicate, so invalld
9. algodaily - y - substring has duplicate, so invalld
10. Now we can start from l, and repeat from step 1... (l, lg, etc.)

We've provided an example of how this brute force solution would look when implemented.

xxxxxxxxxx

}

function hasDuplicateChars(s) {

  const hash = {};

  for (let ch of s) {

    if (hash[ch]) {

      return true;

    } else {

       hash[ch] = 1; 

    }

  }

  return false;

}

​

var lengthOfLongestSubstring = function (s) {

  let max = 0;

  for (let start = 0; start < s.length; start++) {

    for (let end = 0; end < s.length; end++) {  

      const substr = s.slice(start, end + 1);

      if (!hasDuplicateChars(substr)) {

        max = Math.max(max, substr.length);

      }

    }

  }

  return max;

};

​

try {

  assert.equal(lengthOfLongestSubstring('algodaily'), 7);