Question

How to find the longest substring without repeating characters in TypeScript

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: string): string {
    const seen: boolean[] = Array(256).fill(false);

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

    while (right < str.length) {
        const c: number = 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: string = "xwwwqfwwxqwyq";
const result2: string = 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.
 *
 * Time complexity: O(n)
 */
function longestUniqueSubstring(str: string): string {
    const lastSeen: number[] = Array(256).fill(-1);

    let left: number = 0;
    let bestStart: number = 0;
    let bestLength: number = 0;

    for (let right: number = 0; right < str.length; right++) {
        const c: number = 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: number = right - left + 1;
        if (windowLength > bestLength) {
            bestLength = windowLength;
            bestStart = left;
        }
    }

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

const str: string = "xwwwqfwwxqwyq";
const result: string = 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