Longest Repeating Character Replacement - 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 INCLUDED = 'included', INCLUDED_COLOR = 'gold';

function visMainFunction(inputString, k) {
    initClassProperties();

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

    let charFreq = new VisMap();
    let left = 0;
    let right = 0;
    let maxFreq = 0;

    highlightIndex(s, right);
    makeVisVariable(maxFreq).options({ label: 'maxFreq' }).createVis();
    makeVisVariable(k).options({ label: 'k' }).createVis();
    endBatch();

    notification(`📊 <b>Initialization:</b>
        <ul>
            <li><b><code>left = 0</code></b>: Marks the <b>beginning</b> of the current candidate window.  
            Initially points to the start of the string.</li>

            <li><b><code>right = 0</code></b>: Points to the <b>next character</b> to include in the window.  
            Initially also at index <b>0</b>, representing an empty window <code>[left, right)</code>.</li>

            <li><b><code>charFreq = {}</code></b>: A <b>frequency map</b> that keeps track of how many times each character appears within the current window.  
            Starts empty, since no characters have been processed yet.</li>

            <li><b><code>maxFreq = 0</code></b>: Tracks the <b>highest frequency</b> of any single character currently in the window.  
            Initialized to <b>0</b> before any characters are added.</li>

            <li><b><code>k = ${k}</code></b>: The maximum number of characters allowed to be replaced to make all characters in the window identical.</li>
        </ul>
        🪟 The window is currently empty (<code>[0, 0)</code>).
    `);

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

        const rightChar = s[right];

        notification(`📌 <b>Trying to expanding the window</b> by including <b>"${rightChar}"</b>, the character currently pointed to by <b>right</b> at index <b>${right}</b>.`);

        // Update frequency map
        charFreq.set(rightChar, (charFreq.get(rightChar) || 0) + 1);
        maxFreq = Math.max(maxFreq, charFreq.get(rightChar));

        
        notification(`📊 <b>Frequency Updated:</b> Character <b>"${rightChar}"</b> now appears <b>${charFreq.get(rightChar)}</b> time/s in the current window.`);
        
        const windowSize = right - left + 1;
        const replacementsNeeded = windowSize - maxFreq;

        if (replacementsNeeded > k) {
            const leftChar = s[left];
            notification(`⚠️ <b>Window Invalid!</b> The required replacements (<code>windowSize(${windowSize}) − maxFreq(${maxFreq}) = ${replacementsNeeded}</code>) exceed the allowed limit <b>k = ${k}</b>.<br>
                🚪 <b>Cancel the latest expansion</b> but <b>shift the window forward</b> instead by removing <b>"${leftChar}"</b> from the window — decrementing its count and advancing the <b>left</b> pointer.`);

            charFreq.set(leftChar, charFreq.get(leftChar) - 1);
            unhighlightIndex(s, left);
            
            left += 1;
            notification(`📌 <b>Note:</b> After shifting <b>left</b>, the recorded <b>maxFreq</b> remains <b>${maxFreq}</b>, but the true maximum frequency in the window may have decreased since a character was removed.  
                However, this does <b>not</b> affect correctness:<br>
                - The current <b>maxFreq</b> of <b>${maxFreq}</b> already failed to yield a valid window for the present size (<b>${windowSize}</b>).<br>
                - Until <b>maxFreq</b> naturally increases again (a genuine update rather than an overestimation), the window will remain invalid.<br>
                - <b>This guarantees that even if <code>maxFreq</code> is temporarily overestimated, the algorithm never incorrectly accepts an invalid window length.</b>`);
        }

        right += 1;
        highlightIndex(s, right);
        endBatch();
    }

    notification(`🏁 <b>Finished!</b> The length of the longest valid substring is <b>${s.length - left}</b>.`);
    return s.length - left;
}

function highlightIndex(arr, index) {
    arr.makeVisManagerForIndex(index).addClass(INCLUDED);
}

function unhighlightIndex(arr, index) {
    arr.makeVisManagerForIndex(index).removeClass(INCLUDED);
}

function initClassProperties() {
    setClassProperties(INCLUDED, {
        backgroundColor: INCLUDED_COLOR
    });
}

Approach

We solve the problem using a Sliding Window technique with two pointers (left and right) and a frequency map that tracks character counts within the current window. The goal is to find the longest substring where, after replacing at most k characters, all remaining characters in the window become identical.

left: Marks the beginning of the current candidate window.
right: Moves forward to expand the window by examining the next character.

Algorithm Flow:

The process iterates while right has not reached the end of the string.
At the start of each iteration, attempt to expand the window by including s[right]:
- Increment its frequency in the map.
- Update maxFreq — the highest frequency of any single character currently in the window.
Compute:
- windowSize = right − left + 1
- replacementsNeeded = windowSize − maxFreq
If replacementsNeeded ≤ k, the current window is valid and may represent a new maximum length.
If replacementsNeeded > k:
- The current window is invalid. Move left forward to cancel the latest expansion but shift the window instead, and decrease the frequency of s[left] as it leaves the window. This doesn’t necessarily make the window valid immediately — it simply repositions the window while preserving the length of the last valid window, allowing future expansions to be attempted again.
Continue expanding: After adjusting left, increment right to test the next potential expansion.
Throughout the process, right keeps advancing until it reaches the end of the string, while left moves forward only when needed to cancel an invalid expansion. This ensures that the algorithm always preserves the right − left distance of the last valid window—except for the final increment of right that terminates the loop. Therefore, at the end, the length of the longest valid substring equals inputString.length (the final value of right) − left.

Why we don’t need to recompute maxFreq every time:

When left moves forward, maxFreq might become overestimated because removing characters can only reduce their frequency.
This overestimation is harmless:
- The previous maxFreq already failed to make the window valid for its current size.
- Until maxFreq naturally increases again through new additions on the right, the window cannot incorrectly appear valid.
Thus, keeping an occasionally outdated maxFreq preserves correctness while improving efficiency.

🏁 Once the entire string is processed, the window distance from left to the end represents the length of the longest valid substring achievable with at most k replacements.

Time Complexity

Let n be the length of the input string. Both pointers left and right traverse the string at most once.

Each character is added to the window once when right expands.
Each character is removed from the window at most once when left moves forward.
Updating the frequency map and maintaining maxFreq both take O(1) time per operation.

Therefore, the overall time complexity is O(n).

Space Complexity

The algorithm maintains a frequency map (charFreq) that stores the count of each character currently inside the window. Since s consists of only uppercase English letters, the map can store at most 26 entries, which is asymptotically O(1).

All other variables (left, right, maxFreq) also use O(1) space. Hence, the total auxiliary space is O(1).

Input-1

Input-2

Longest Repeating Character Replacement - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity