Question

How to find the longest substring without repeating characters in JavaScript

Answer 1

function findLongestSubstringWithoutRepeatingCharacters(str) {
    const str_size = str.length;
    let start = 0, end = 0;
    let start_sub = 0, end_sub = 0;
    let ASCII = Array(256).fill(0);

    while (end < str_size) {
        if (ASCII[str[end].charCodeAt(0)] > 0) {
            while (str[start] != str[end]) {
                ASCII[str[start].charCodeAt(0)] = 0;
                start++;
            }
            start++;
        }
        else {
            ASCII[str[end].charCodeAt(0)] = end + 1;
            if (end - start > end_sub - start_sub) {
                start_sub = start;
                end_sub = end;
            }
        }
        end++;
    }
    
    for (let i = start_sub; i <= end_sub; i++) {
        console.log(str[i]);
    }
}

const str = "xwwwqfwwxqwyq";

findLongestSubstringWithoutRepeatingCharacters(str);




/*
run:
   
"x"
"q"
"w"
"y"

*/

 

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

Answer 3

/*
 * 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