Length of the longest substring without repeating characters

This problem was asked by Yahoo.

You are given a string, find the length of the longest substring without repeating characters.

Example

function lengthOfLongestSubstring(string){

}

console.log(lengthOfLongestSubstring('abcabcbb')); // 3
console.log(lengthOfLongestSubstring('bbbbb')); // 1
console.log(lengthOfLongestSubstring('pwwkew')); // 3

Solution

function lengthOfLongestSubstring(str) {
  let start = 0;
  let longest = 0;
  const seen = {};
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    if (seen[char]) {
      start = Math.max(start, seen[char]);
    }
    longest = Math.max(longest, i - start + 1);
    seen[char] = i + 1;
  }
  return longest;
}

Explanation

1. Initialize a seen object to track characters we've encountered before
2. Initialize start to track the start of the current substring
3. Iterate through each character in the string
4. If we've seen this character before, update start to be the maximum of the current start or the last index for this character
5. Update longest to be the max of itself or the current substring length
6. Store the index + 1 of the current character in seen
7. After iterating through all characters, longest will be the length of the longest substring without repeating characters.