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

Examples:

  • Given "abcabcbb", the answer is "abc"
  • Given "bbbbb", the answer is "b"
  • Given "stackoverflow", the answer is "stackoverfl"

This is a version of the Longest common subsequence problem.


Brute Force

A Brute Force approach is to loop through the string twice, checking every substring against every other substring and finding the maximum length where the substring is unique. We’ll need two functions: one to check if a substring is unique and a second function to perform our double loop.

const allUnique = str => {
  const set = [...new Set(str)];
  return (set.length === str.length) ? true: false;
}

const lengthOfLongestSubstring = str => {
  let result = 0,
      maxResult = 0;
  for (let i=0; i<str.length-1; i++) {
    for (let j=i+1; j<str.length; j++) {
      if (allUnique(str.substring(i, j))) {
        result = str.substring(i, j).length;
        if (result > maxResult) {
          maxResult = result;
        }
      }
    }
  return maxResult;
  }
}

The resulting time complexity is O(n^3) since lengthOfLongestSubstring uses two loops which is O(n^2) and allUnique also uses one loop O(n) each time.

Greedy Approach

A better approach is to loop through only once and keep track of the maximum unique substring length as we go. We can use either an array or a hash map, but I think the new .includes() array method is cool, so let’s use that.

// O(n) time, O(1) space
const lengthOfLongestSubstring = str => {
  let result = [],
      maxResult = 0;

  for (let i=0; i<str.length; i++) {
    if (!result.includes(str[i])) {
      result.push(str[i]);
    } else {
      maxResult = i;
    }
  }

  return maxResult;
}




Want to improve your JavaScript? I have a list of recommended JavaScript books.