Longest Substring Without Repeating Characters - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const LEFT = 'left_ptr', LEFT_COLOR = 'gold';
const RIGHT = 'right_ptr', RIGHT_COLOR = 'blue';
const CLOSED = 'closed';

function visMainFunction(inputString) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const s = VisArray.from([...inputString]);

    let charSet = new VisSet();
    let left = 0;
    let maxLength = 0;

    let right = 0;
    s.makeVisManagerForIndex(0).addClass(RIGHT).addClass(LEFT);
    makeVisVariable(maxLength).options({ label: 'maxLength' }).createVis();
    endBatch();

    notification(`📊 <b>Initial State:</b>
        <ul>
            <li><b><code>${makeColoredSpan('left', LEFT_COLOR)}</code></b>: start index of the current valid substring <b>(inclusive)</b>.</li>
            <li><b><code>${makeColoredSpan('right', RIGHT_COLOR)}</code></b>: index of the character we are about to include.  
            While <code>s[right]</code> is not yet added, the window is half-open <code>[left, right)</code>.  
            After adding <code>s[right]</code> (before moving the pointer), the window becomes <code>[left, right]</code>.
            </li>
            <li><b><code>charSet</code></b>: a <b>set</b> that stores all characters currently inside the window.</li>
            <li><b><code>maxLength</code></b>: keeps track of the <b>maximum length</b> of any valid substring found so far (initially <b>0</b>).</li>
        </ul>
        🪟 Initially, both pointers are at index <b>0</b>, representing an empty window <code>[0, 0)</code>.  
        The algorithm will now dynamically <b>expand</b> and <b>shrink</b> this window to find the longest substring without repeating characters.`);

    while (right < s.length) {
        startPartialBatch();

        const rightChar = s[right];

        notification(`📌 <b>${makeColoredSpan('Right Pointer', RIGHT_COLOR)} at index ${makeColoredSpan(String(right), RIGHT_COLOR)}:</b> Character = <b>"${rightChar}"</b>.`);
        
        if (charSet.has(rightChar)) {
            notification(`⚠️ <b>Cannot extend the window yet!</b> The character <b>"${rightChar}"</b> is already in the current substring.<br>
                🔄 Move <b>${makeColoredSpan('left', LEFT_COLOR)}</b> forward to shrink the window until <b>"${rightChar}"</b> is no longer in the substring — 
                only then can it be safely included.`);
        }

        while (charSet.has(rightChar)) {
            startPartialBatch();
            const leftChar = s[left];

            notification(`🚪 <b>Shrinking window:</b> Removing <b>"${leftChar}"</b> at index <b>${makeColoredSpan(String(left), LEFT_COLOR)}</b> 
                and continuing to shrink until <b>"${rightChar}"</b> is no longer in the substring — 
                ensuring it can be safely included again.`);
            charSet.delete(leftChar);
            left += 1;
            moveHighlight(s, left, LEFT);
            endBatch();
        }

        notification(`✅ <b>Expanding window:</b> Added '${rightChar}', forming a valid substring from ${makeColoredSpan(String(left), LEFT_COLOR)} to ${makeColoredSpan(String(right), RIGHT_COLOR)}.`);
        excludeRight(s, right);
        charSet.add(rightChar);

        const newLength = right - left + 1;
        if (newLength > maxLength) {
            maxLength = newLength;
            notification(`🌟 <b>New Maximum Length Found:</b> ${maxLength}.`);
        }

        right += 1;
        moveHighlight(s, right, RIGHT);
        endBatch();
    }

    notification(`🏁 <b>Finished!</b> The length of the longest substring without repeating characters is <b>${maxLength}</b>.`);
    return maxLength;
}

function moveHighlight(arr, index, className) {
    const manager = arr.makeVisManagerForIndex(index-1).removeClass(className);
    if (className === RIGHT) manager.removeClass(CLOSED);
    arr.makeVisManagerForIndex(index).addClass(className);
}

function excludeRight(arr, index) {
    arr.makeVisManagerForIndex(index).addClass(CLOSED);
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Legend</b>
        <ul>
            <li>
            <b>${makeColoredSpan('Gold background', LEFT_COLOR)}</b>:  
            Highlights the <b>Left Pointer</b> — the start index of the current valid substring <b>(inclusive)</b>.  
            It moves forward when the window needs to shrink to remove characters and restore validity.
            </li>
            <li>
            <b>${makeColoredSpan('Blue dashed border', RIGHT_COLOR)}</b>:  
            Indicates the <b>Right Pointer</b> — the next character being considered for inclusion.  
            Before adding this character, the window is <b>half-open</b> (<code>[left, right)</code>).
            </li>
            <li>
            <b>${makeColoredSpan('Blue solid border', RIGHT_COLOR)}</b>:  
            Marks that the <b>Right Pointer’s character has been included</b> in the substring,  
            temporarily changing the window to <b>[left, right]</b> until <code>right</code> moves forward again.
            </li>
        </ul>
        🪟 Together, these colors show the dynamic <b>expansion</b> and <b>contraction</b> of the sliding window:  
        the gold background tracks the <b>start</b>, and the blue border (dashed or solid) tracks the <b>end</b> 
        as it switches between candidate and included states.
    `);
}

function initClassProperties() {
    setClassProperties(LEFT, {
        backgroundColor: LEFT_COLOR
    });
    setClassProperties(RIGHT, {
        borderColor: RIGHT_COLOR,
        borderDasharray: '5,5'
    });
    setClassProperties(CLOSED, {
        borderDasharray: '0'
    })
}

Approach

We scan the string with a sliding window bounded by two pointers, left and right, and a set that stores the characters currently inside the window (i.e., the current valid substring with no repeats). The variable maxLength tracks the best length seen so far.

Pointers:
- left: start index of the current valid substring (inclusive).
- right: index of the character we are about to include. While s[right] is not yet added, the window is half-open [left, right). Immediately after adding s[right] (and before advancing right), the window becomes [left, right]. We then increment right to restore the half-open form for the next iteration.
Data structure: a set charSet to test membership in O(1) and to add/remove characters as the window moves.
Main loop (while right < s.length):
1. Read candidate: let rightChar = s[right].
2. Resolve conflict (shrink from the left): While rightChar is already present in charSet (meaning that character exists somewhere in the current window), shrink the window from the left by removing s[left] from the set and incrementing left until rightChar is no longer in the window — making it safe to expand the window from the right.
3. Extend window: add rightChar to charSet. The window [left, right] is now a valid substring with all unique characters.
4. Update answer: compute newLength = right - left + 1; if larger than maxLength, update maxLength.
5. Advance: increment right to examine the next character.
Why this works: the window always contains unique characters. On a conflict, we discard the minimal prefix needed (by moving left) to make the new character admissible, then continue to grow. Each character is added and removed at most once, so the process is linear.
Result: when the loop finishes, maxLength is the length of the longest substring without repeating characters.

Time Complexity

Let n be the length of the string. Each character is added to the set at most once and removed at most once as the window slides. Both pointers (left and right) move forward at most n times total. Therefore, the running time is O(n).

Space Complexity

We store at most one instance of each unique character from the current substring in charSet. Therefore, the auxiliary space is O(m), where m is the number of unique characters in the input string s — note that m cannot exceed the size of the character alphabet.

Input-1

Longest Substring Without Repeating Characters - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity