Question

How to find the longest substring without repeating characters in Node.js

Answer 1

/*
 * Finds the longest substring without repeating characters.
 * This version keeps a presence table and shrinks the window
 * by clearing characters until the duplicate is removed.
 *
 * Time complexity: O(n)
 */
function longestUniqueSubstringASCII(str) {
  const seen = Array(256).fill(false); // ASCII presence table

  let left = 0;
  let right = 0;
  let bestLeft = 0;
  let bestRight = 0;

  while (right < str.length) {
    const c = str.charCodeAt(right);

    if (seen[c]) {
      // Shrink window until we remove the duplicate
      while (str[left] !== str[right]) {
        seen[str.charCodeAt(left)] = false;
        left++;
      }
      left++; // skip the duplicate itself
    } else {
      seen[c] = true;

      if (right - left > bestRight - bestLeft) {
        bestLeft = left;
        bestRight = right;
      }
    }

    right++;
  }

  return str.slice(bestLeft, bestRight + 1);
}

const str2 = "xwwwqfwwxqwyq";
const result2 = longestUniqueSubstringASCII(str2);

console.log("Input:", str2);
console.log("Longest substring without repeating characters:", result2);



/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals

Answer 2

/*
 * Finds the longest substring without repeating characters.
 * Uses a sliding window and a table of last-seen indexes.
 *
 * - lastSeen[c] stores the most recent index of character c.
 * - left/right define the current window.
 * - When a duplicate appears inside the window, move left forward.
 *
 * Time complexity: O(n)
 */
function longestUniqueSubstring(str) {
  const lastSeen = Array(256).fill(-1); // ASCII table

  let left = 0;
  let bestStart = 0;
  let bestLength = 0;

  for (let right = 0; right < str.length; right++) {
    const c = str.charCodeAt(right);

    // If character was seen inside the current window, move left
    if (lastSeen[c] >= left) {
      left = lastSeen[c] + 1;
    }

    // Update last-seen index
    lastSeen[c] = right;

    // Check if this window is the best so far
    const windowLength = right - left + 1;
    if (windowLength > bestLength) {
      bestLength = windowLength;
      bestStart = left;
    }
  }

  return str.slice(bestStart, bestStart + bestLength);
}

const str = "xwwwqfwwxqwyq";
const result = longestUniqueSubstring(str);

console.log("Input:", str);
console.log("Longest substring without repeating characters:", result);



/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals