Longest distinct substring algorithm in JavaScript

2014-01-09 (Thursday) | 200 words (~1 minutes reading)

Given a string, find the longest substring of distinct characters.

function findLongestDistinctSubstring(text) {
  const lastPos = {};
  let maxLength = 0;
  let left = 0;
  for (let right = 0; right < text.length; right++) {
    const char = text[right];
    if (char in lastPos) {
      // Can't go backwards, so use max() to ensure
      left = Math.max(left, lastPos[char] + 1);
    }
    lastPos[char] = right;
    maxLength = Math.max(maxLength, (right - left) + 1);
  }
  return maxLength;
}

This solution has $O(n)$ time complexity because we iterate the input string once, and $O(n)$ space complexity because we build up a mapping of input characters to positions.


Tech mentioned