Longest Common Subsequence - JS Solution (2D dp array)

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 CURRENT_INPUT_INDEX = 'current_input_index', CURRENT_INPUT_INDEX_COLOR = 'gold';
const REUSING_1 = 'reusing_1', REUSING_1_COLOR = 'orange';
const REUSING_2 = 'reusing_2', REUSING_2_COLOR = 'blue';
const IN_PROGRESS = 'in_progress', IN_PROGRESS_COLOR = 'gray';
const DONE = 'done', DONE_COLOR = 'green';

function visMainFunction(inputText1, inputText2) {
    initClassProperties();

    startBatch();
    const text1 = VisArray.from([...inputText1]);
    const text2 = VisArray.from([...inputText2]);

    const text1Len = text1.length, text2Len = text2.length;

    const rows = Array.from({ length: text1Len + 1 }, () => new VisArray(text2Len + 1).fill(0));
    const dp = new VisArray2D(...rows).options({ label: 'LCS DP Table' });
    highlightFirstRowAndCol(dp, DONE);

    let rowIndex = 1;
    makeVisVariable(rowIndex).registerAsIndexPointer(text1, CURRENT_INPUT_INDEX, (val) => val - 1);
    endBatch();

    explanationAndColorPaletteNotifications();

    notification(`
        ⚙️ <b>Initialization</b><br/>
        • Created the DP table <code>dp</code> with size <b>(${text1Len + 1}) × (${text2Len + 1})</b>, all <code>0</code>.<br/>
        • Marked the first <b>row</b> and <b>column</b> as ${makeColoredSpan('done (0 = empty-prefix LCS)', DONE_COLOR)} — LCS is <b>0</b> when at least one string is empty.<br/><br/>
        🔁 <b>Iteration Pointers</b><br/>
        • ${makeColoredSpan('rowIndex', CURRENT_INPUT_INDEX_COLOR)} starts at <b>1</b> to scan <code>text1</code> (top → bottom).<br/>
        • ${makeColoredSpan('colIndex', CURRENT_INPUT_INDEX_COLOR)} will restart at <b>1</b> for each row to scan <code>text2</code> (left → right).<br/><br/>
        🎯 <b>What we will compute</b><br/>
        • Each cell ${makeColoredSpan('dp[i][j]', IN_PROGRESS_COLOR)} stores the LCS length of 
            <code>text1[0..i-1]</code> and <code>text2[0..j-1]</code>.<br/>
        • While a cell is being computed it is treated as ${makeColoredSpan('in progress', IN_PROGRESS_COLOR)}; once finalized it becomes ${makeColoredSpan('done', DONE_COLOR)}.<br/><br/>
        🚀 <b>Starting the DP fill</b>: iterate rows <code>i = 1..${text1Len}</code> and, for each row, columns <code>j = 1..${text2Len}</code>.
    `);

    while (rowIndex <= text1Len) {
        const char1 = text1[rowIndex - 1];

        let colIndex = 1;
        makeVisVariable(colIndex).registerAsIndexPointer(text2, CURRENT_INPUT_INDEX, (val) => val - 1);

        while (colIndex <= text2Len) {
            startPartialBatch();

            const char2 = text2[colIndex - 1];

            const indexPairVisManager = dp.makeVisManagerForIndexPair(rowIndex, colIndex);
            indexPairVisManager.addClass(IN_PROGRESS);

            notification(`
                🧮 Computing ${makeColoredSpan(`dp[${rowIndex}][${colIndex}]`, IN_PROGRESS_COLOR)} — 
                LCS of <code>text1[0..${rowIndex - 1}]</code> and <code>text2[0..${colIndex - 1}]</code>.
            `);
            notification(`
                📌 Comparing the <b>current characters</b> of both strings:<br/>
                <code>text1[${rowIndex - 1}] = '${char1}'</code> vs. 
                <code>text2[${colIndex - 1}] = '${char2}'</code>.
            `);

            if (char1 === char2) {
                const undoHighlightUtilizedIndexPairs = highlightUtilizedIndexPairs(
                    dp, 
                    [[rowIndex - 1, colIndex - 1]], 
                    [REUSING_1]
                );

                notification(`
                  ✅ <b>Match:</b> characters are equal (<code>'${char1}'</code>).<br/>
                  • Use the ${makeColoredSpan('diagonal', REUSING_1_COLOR)} value <code>dp[${rowIndex - 1}][${colIndex - 1}]</code> because it counts the LCS <i>excluding</i> these matching current chars.<br/>
                  • We can extend the LCS represented by that cell by adding this matching character → dp[${rowIndex}][${colIndex}] = dp[${rowIndex - 1}][${colIndex - 1}] + 1.
                `);

                dp[rowIndex][colIndex] = dp[rowIndex - 1][colIndex - 1] + 1;
                undoHighlightUtilizedIndexPairs();
            } else {
                const undoHighlightUtilizedIndexPairs = highlightUtilizedIndexPairs(
                    dp, 
                    [[rowIndex - 1, colIndex], [rowIndex, colIndex - 1]], 
                    [REUSING_1, REUSING_2]
                );

                notification(`
                  ❌ <b>No match:</b> characters differ.<br/>
                  • Consider ${makeColoredSpan('up', REUSING_1_COLOR)} <code>dp[${rowIndex - 1}][${colIndex}]</code> — best LCS if we <b>exclude</b> the current char of <code>text1</code>, i.e., <code>text1[${rowIndex - 1}]</code>.<br/>
                  • Consider ${makeColoredSpan('left', REUSING_2_COLOR)} <code>dp[${rowIndex}][${colIndex - 1}]</code> — best LCS if we <b>exclude</b> the current char of <code>text2</code>, i.e., <code>text2[${colIndex - 1}]</code>.<br/>
                  • The optimal choice is the larger of the two (since the current characters don’t match, we keep the longer subsequence excluding the current character from either string.) → 
                    <code>dp[${rowIndex}][${colIndex}] = max(${dp[rowIndex - 1][colIndex]}, ${dp[rowIndex][colIndex - 1]})</code>.
                `);

                dp[rowIndex][colIndex] = Math.max(dp[rowIndex - 1][colIndex], dp[rowIndex][colIndex - 1]);
                undoHighlightUtilizedIndexPairs();
            }

            indexPairVisManager.addClass(DONE);
            indexPairVisManager.removeClass(IN_PROGRESS);
            colIndex += 1;
            endBatch();
        }

        rowIndex += 1;
    }

    notification(`
      🏁 <b>Finished!</b> The LCS length is <b>${dp[text1Len][text2Len]}</b>.
    `);
    return dp[text1Len][text2Len];
}

function initClassProperties() {
    setClassProperties(CURRENT_INPUT_INDEX, { backgroundColor: CURRENT_INPUT_INDEX_COLOR });
    setClassProperties(REUSING_1, { backgroundColor: REUSING_1_COLOR });
    setClassProperties(REUSING_2, { backgroundColor: REUSING_2_COLOR });
    setClassProperties(IN_PROGRESS, { backgroundColor: IN_PROGRESS_COLOR });
    setClassProperties(DONE, { backgroundColor: DONE_COLOR });
}

function highlightUtilizedIndexPairs(arr, pairs, classNames) {
    startBatch();
    pairs.forEach((pair, index) => {
        const [rowIndex, colIndex] = pair;
        const visManager = arr.makeVisManagerForIndexPair(rowIndex, colIndex);        
        visManager.addClass(classNames[index]);
        visManager.removeClass(DONE);
    });
    endBatch();

    return () => {
        startBatch();
        pairs.forEach((pair, index) => {
            const [rowIndex, colIndex] = pair;
            const visManager = arr.makeVisManagerForIndexPair(rowIndex, colIndex);
            visManager.addClass(DONE);
            visManager.removeClass(classNames[index]);
        });
        endBatch();
    };
} 

function highlightFirstRowAndCol(arr, highlightClass) {
    const numOfRows = arr.length;
    if (numOfRows === 0) return;

    const numOfCols = arr[0].length;

    for (let rowIndex = 0; rowIndex < numOfRows; rowIndex++) {
        arr.makeVisManagerForIndexPair(rowIndex, 0).addClass(highlightClass);
    }

    for (let colIndex = 0; colIndex < numOfCols; colIndex++) {
        arr.makeVisManagerForIndexPair(0, colIndex).addClass(highlightClass);
    }
}

function explanationAndColorPaletteNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Palette & Legend</b><br/>
        • ${makeColoredSpan('text1[i] / text2[j]', CURRENT_INPUT_INDEX_COLOR)} — the <b>current input characters</b> being compared.<br/>
        • ${makeColoredSpan('dp[i-1][j-1]', REUSING_1_COLOR)} — the <b>diagonal</b> cell, representing the LCS of prefixes <b>excluding both current characters</b>.<br/>
        • ${makeColoredSpan('dp[i-1][j]', REUSING_1_COLOR)} — the <b>up</b> cell, representing the LCS if we <b>exclude</b> the current character of <code>text1</code>.<br/>
        • ${makeColoredSpan('dp[i][j-1]', REUSING_2_COLOR)} — the <b>left</b> cell, representing the LCS if we <b>exclude</b> the current character of <code>text2</code>.<br/>
        • ${makeColoredSpan('dp[i][j]', IN_PROGRESS_COLOR)} — the <b>current DP cell</b> being <b>computed</b>.<br/>
        • ${makeColoredSpan('finalized dp cells', DONE_COLOR)} — cells whose <b>LCS value has been determined</b>.<br/><br/>
    `);
}

Approach

Approach (LCS via Dynamic Programming)

We use a Dynamic Programming (DP) approach to compute the length of the Longest Common Subsequence (LCS) between two strings text1 (length m) and text2 (length n). The idea is to build a 2D DP table dp where dp[i][j] represents the length of the LCS between the first i characters of text1 (text1[0..i-1]) and the first j characters of text2 (text2[0..j-1]).

Initialization

Create a DP table of size (m + 1) × (n + 1) initialized with 0.
The first row (i = 0) and first column (j = 0) remain 0, since an empty prefix of either string means there can be no common subsequence — i.e., the LCS length is 0 when at least one of the strings is empty.

Transition & Meaning of Neighboring Cells

To compute dp[i][j], we compare the current characters text1[i-1] and text2[j-1] and refer to three neighboring cells:

dp[i-1][j-1] (diagonal) — LCS of prefixes excluding the current characters text1[i-1] and text2[j-1].
dp[i-1][j] (up) — best LCS if we exclude the current character of text1 (text1[i-1]) while keeping text2[0..j-1].
dp[i][j-1] (left) — best LCS if we exclude the current character of text2 (text2[j-1]) while keeping text1[0..i-1].

Transition Rules

Case 1 — Match: If text1[i-1] === text2[j-1], the current characters match. This means we can extend the LCS found so far by one character:

• Use the diagonal value dp[i-1][j-1] because it counts the LCS excluding these matching characters.
• Add +1 to include the current matching character:
dp[i][j] = dp[i-1][j-1] + 1.

Case 2 — No Match: If text1[i-1] !== text2[j-1], the current characters differ, so we cannot include both. Instead, we take the better of two possibilities:

• Consider the up cell dp[i-1][j] — best LCS if we exclude the current character of text1 (text1[i-1]).
• Consider the left cell dp[i][j-1] — best LCS if we exclude the current character of text2 (text2[j-1]).
• The optimal choice is the larger of the two — since the current characters don’t match, we keep the longer subsequence excluding the current character from either string:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Iteration Order & Visualization Cues

Fill the DP table row by row for i = 1..m, and within each row, process each column for j = 1..n. (We start from 1 for both since i = 0 and j = 0 represent empty prefixes, already initialized to 0.)
While computing a cell, it can be visualized as in progress; once finalized, mark it as done.

Result

After filling the entire table, the length of the Longest Common Subsequence is given by the bottom-right cell: dp[m][n].

Time Complexity

O(m × n), where m = text1.length and n = text2.length.

We fill a DP table of size (m + 1) × (n + 1), computing each cell in constant time O(1). Therefore, the total running time grows linearly with the number of cells, resulting in O(m × n).

Space Complexity

No content provided

Input-1

Longest Common Subsequence - JS Solution (2D dp array)

Solution code

Solution explanation

Solution explanation

Approach

Approach (LCS via Dynamic Programming)

Initialization

Transition & Meaning of Neighboring Cells

Transition Rules

Iteration Order & Visualization Cues

Result

Time Complexity

Space Complexity