Longest Common Subsequence - JS Solution Space Optimized

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'; // diagonal / up
const REUSING_2 = 'reusing_2', REUSING_2_COLOR = 'blue';   // left
const IN_PROGRESS = 'in_progress', IN_PROGRESS_COLOR = 'gray';
const DONE = 'done', DONE_COLOR = 'green';

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

  if (inputText1.length < inputText2.length) {
    [inputText1, inputText2] = [inputText2, inputText1];
    notification(`
        🔄 <b>Optimization Step</b><br/>
        • Swapped the two input strings so that <code>text1</code> is the longer one.<br/>
        • This allows the single-row buffer <code>dpRow</code> to be allocated for the <b>shorter string</b> → saving space to <b>O(min(m, n))</b>.<br/>
        • The logic and final LCS length remain exactly the same.
    `);
  }

  startBatch();
  const text1 = VisArray.from([...inputText1]).options({ label: 'text1' });
  const text2 = VisArray.from([...inputText2]).options({ label: 'text2' });
  
  const m = text1.length, n = text2.length;

  // Single-row buffer:
  // For a fixed i (processing text1[i-1]), dpRow[j] holds the LCS length for prefixes
  // text1[0..i-1] and text2[0..j-1] AFTER it is updated in this row.
  // Before updating dpRow[j] in the current row, it still holds the value from the previous row.
  const dpRow = new VisArray(n + 1).fill(0).options({ label: 'dpRow (1D LCS)' });

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

  explanationAndColorPaletteNotifications(m, n);

  notification(`
    ⚙️ <b>Initialization</b><br/>
    • Using a single-row buffer <code>dpRow</code> of size <b>${n + 1}</b>, all <code>0</code>.<br/>
    • This row-0 state represents the base case (empty prefix of <code>text1</code>): LCS is <code>0</code> for all prefixes of <code>text2</code>.<br/><br/>
    🔁 <b>Iteration Pointers</b><br/>
    • ${makeColoredSpan('rowIndex', CURRENT_INPUT_INDEX_COLOR)} iterates <b>1..${m}</b> over <code>text1</code>.<br/>
    • ${makeColoredSpan('colIndex', CURRENT_INPUT_INDEX_COLOR)} iterates <b>1..${n}</b> over <code>text2</code> for each row.<br/><br/>
    ✅ <b>Row invariant</b><br/>
    • After completing row <code>rowIndex</code>, each <code>dpRow[colIndex]</code> equals 
      <code>LCS(text1[0..rowIndex-1], text2[0..colIndex-1])</code>.<br/><br/>
    🚀 <b>Start the 1D update</b>.
`);

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

    startBatch();
    let colIndex = 1;
    dpRow.makeVisManagerForIndex(0).addClass(DONE);
    makeVisVariable(colIndex).registerAsIndexPointer(text2, CURRENT_INPUT_INDEX, (val) => val - 1);

    // At the start of a new row, the "diagonal" carried value corresponds to the
    // LCS of text1[0..(i-2)] and text2[0..-1] (i.e., 0).
    let diagonal = 0;
    makeVisVariable(diagonal).options({ label: 'diagonal' }).createVis();
    endBatch();

    notification(`
        ▶️ <b>Processing row ${rowIndex}</b> — fixing the prefix 
        <code>text1[0..${rowIndex - 1}]</code> 
        (ending with <code>'${char1}'</code>) and 
        <b>updating <code>dpRow</code> for this row</b>.<br/>
        Currently, <code>dpRow</code> still holds the LCS values from the 
        <b>previous row</b> (for the prefix <code>text1[0..${rowIndex - 2}]</code>).<br/>
        As we proceed, we’ll rely on the fact that values from the previous row 
        remain stored in <code>dpRow</code> until we overwrite them — 
        allowing us to reuse them whenever we need the 
        <b>“up”</b> cell (the result for the same column in the previous row).<br/><br/>
        Before starting, we also <b>reset the diagonal</b> to <code>0</code>, 
        since all the LCS values are <code>0</code> for <b>column 0</b>.
    `);

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

      const char2 = text2[colIndex - 1];

      // Values BEFORE we write dpRow[colIndex] for this row:
      // up   = value from the previous row at this column
      // left = value we already computed in this row for the previous column
      const up   = dpRow[colIndex];
      makeVisVariable(up).options({label: 'up'}).createVis();

      const currVM = dpRow.makeVisManagerForIndex(colIndex).addClass(IN_PROGRESS);
      notification(`
        🧮 Computing LCS for prefixes 
        <code>text1[0..${rowIndex - 1}]</code> and <code>text2[0..${colIndex - 1}]</code> (1D update).<br/>
        📌 Compare current characters: 
        <code>text1[${rowIndex - 1}] = '${char1}'</code> vs <code>text2[${colIndex - 1}] = '${char2}'</code>.<br/><br/>
        Before updating this position, <code>dpRow[${colIndex}]</code> still holds the LCS value 
        for the <b>same column from the previous row</b>, which we can safely read as the 
        current <b>“up”</b> value.<br/>
        We also keep a separate <b>stored copy</b> of this value in a variable so that after we use it, 
        it can become the next <b>diagonal</b> value when we move to the next column.
        `);

      if (char1 === char2) {
        notification(`
            ✅ <b>Match:</b> characters are equal (<code>'${char1}'</code>).<br/>
            • Use the carried ${makeColoredSpan('diagonal', REUSING_1_COLOR)} value — it represents the LCS 
                length for both prefixes <b>excluding</b> the current characters being compared.<br/>
            • Since these two characters match, we can <b>extend</b> that subsequence by including this common character:<br/>
                <code>newValue = diagonal + 1</code> → the LCS length increases by <b>1</b>.<br/>
            • Update <code>dpRow[${colIndex}]</code> to reflect this extended subsequence length.
        `);

        dpRow[colIndex] = diagonal + 1;
        currVM.removeClass(IN_PROGRESS).addClass(DONE);
      } else {
        const upVM   = dpRow.makeVisManagerForIndex(colIndex).addClass(REUSING_1);
        const leftVM = dpRow.makeVisManagerForIndex(colIndex - 1).removeClass(DONE).addClass(REUSING_2);

        notification(`
            ❌ <b>No match:</b> characters differ.<br/>
            • Consider the ${makeColoredSpan('up', REUSING_1_COLOR)} value we saved earlier — 
                it comes from the <b>previous row</b> (the same column) and represents the best LCS 
                if we <b>exclude</b> the current character of <code>text1</code>.<br/>
            • Consider the ${makeColoredSpan('left', REUSING_2_COLOR)} value — the <b>current-row</b> result 
                for the previous column (<code>dpRow[${colIndex - 1}]</code>), which represents excluding 
                the current character of <code>text2</code>.<br/>
            • The optimal choice is the <b>larger</b> of these two values: since the current characters don’t match, 
                we keep the longer subsequence excluding one of them.<br/>
                <code>dpRow[${colIndex}] = max(${makeColoredSpan('up', REUSING_1_COLOR)}, ${makeColoredSpan('left', REUSING_2_COLOR)})</code>.<br/>
            • This updated value now represents the LCS length for 
                <code>text1[0..${rowIndex - 1}]</code> and <code>text2[0..${colIndex - 1}]</code>.
        `);

        dpRow[colIndex] = Math.max(up, dpRow[colIndex - 1]);

        upVM.removeClass(REUSING_1);
        leftVM.removeClass(REUSING_2).addClass(DONE);
        currVM.removeClass(IN_PROGRESS).addClass(DONE);
      }

      notification(`
      ↪️ <b>Update carried diagonal</b><br/>
      • Before moving to the next column, we store the current ${makeColoredSpan('up', REUSING_1_COLOR)} value 
        (the one that belonged to the same column in the previous row).<br/>
      • This becomes the new ${makeColoredSpan('diagonal', REUSING_1_COLOR)} for the next column, 
        since in the next iteration it will represent the LCS excluding both current characters of that next pair.<br/>
      • In other words, we are <b>shifting</b> our diagonal reference forward along the row.
    `);
      diagonal = up;

      colIndex += 1;
      endBatch();
    }

    clearDoneClasses(dpRow);
    rowIndex += 1;
  }

  notification(`
    🏁 <b>Finished!</b> The LCS length for the full strings is <b>${dpRow[n]}</b> (stored in <code>dpRow[${n}]</code>).
  `);
  return dpRow[n];
}

// ===== Styles =====
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, { borderColor: IN_PROGRESS_COLOR, borderDasharray: '5,5' });
  setClassProperties(DONE, { backgroundColor: DONE_COLOR });
}

function clearDoneClasses(dpRow) {
  startBatch();
  for (let i = 0; i < dpRow.length; i++) {
    dpRow.makeVisManagerForIndex(i).removeClass(DONE);
  }
  endBatch();
}

// ===== Shared explanation & legend (pure 1D wording) =====
function explanationAndColorPaletteNotifications(m, n) {
  explanationNotification();
  notification(`
    🎨 <b>Color Palette & Legend</b><br/>
    • ${makeColoredSpan('text1[rowIndex-1] / text2[colIndex-1]', CURRENT_INPUT_INDEX_COLOR)} — the <b>current input characters</b> being compared.<br/>
    • ${makeColoredSpan('diagonal (carried)', REUSING_1_COLOR)} — LCS length of both prefixes before including the current characters; carried to the next column.<br/>
    • ${makeColoredSpan('up (dpRow[j] before overwrite)', REUSING_1_COLOR)} — value from the previous row at the same column (exclude current <code>text1</code> char).<br/>
    • ${makeColoredSpan('left (dpRow[j-1])', REUSING_2_COLOR)} — value from the current row at the previous column (exclude current <code>text2</code> char).<br/>
    • ${makeColoredSpan('in-progress entry', IN_PROGRESS_COLOR)} — the prefix-pair currently being computed in-place (shown with a dashed border).<br/>
    • ${makeColoredSpan('done entry', DONE_COLOR)} — the position in <code>dpRow</code> whose updated LCS value has been finalized for this iteration.<br/>
  `);
}

Approach

Approach (Space-Optimized Dynamic Programming)

We compute the Longest Common Subsequence (LCS) length using a 1-row dynamic programming approach that stores only the necessary information from the previous iteration. To minimize the buffer size, we first ensure that text1 is the longer string—if not, we swap them.

Let m be the text1.length and n text2.length (after the swap if necessary).
Initialize a 1D array dpRow of length n + 1 with all values set to 0. This corresponds to the base case (row 0), where the LCS length is 0 for all prefixes of text2. After each iteration over a character of text1, dpRow[j] represents the LCS length between the processed prefix text1[0..i-1] and the prefix text2[0..j-1]. The array is updated in place as we move through each character of text1.

Iteration Logic

We update dpRow for each character in text1 (for row index 1..m). For each character text1[rowIndex-1], we iterate over all characters in text2 (for column index 1..n) and update dpRow[colIndex] in place. The values already stored in dpRow come from the previous text1 character and remain valid until they are overwritten, allowing us to reuse them directly during the current update.

Variables Used During Each Update

diagonal — a carried variable representing the LCS length before including the current characters. It starts at 0 at the beginning of each new iteration over text1, because column 0 corresponds to empty prefixes.
up — the value currently in dpRow[colIndex] before we overwrite it. This represents the LCS length if we exclude the current character of text1 (i.e., what we had from the previous iteration for the same j).
left — the already updated dpRow[colIndex-1], which corresponds to excluding the current character of text2.

Transition Rules

Match: if text1[i-1] === text2[j-1], we extend the previous best subsequence (stored in diagonal) by this matching character: dpRow[j] = diagonal + 1.
No Match: if the characters differ, we cannot include both current characters. We keep the longer subsequence found so far by excluding one of them: dpRow[j] = max(up, left).

After computing dpRow[j], we assign diagonal = up to carry forward the “old” value for the next column, since in the next step that will represent the case where both current characters were excluded.

Row Processing Flow

For each prefix of text1:

Start with diagonal = 0 (LCS is 0 for column 0).
At every position j, read the up value directly from dpRow[j] before it’s overwritten — it still holds the old value from the previous iteration.
After updating dpRow[j], assign diagonal = up before moving to the next j.
Once this iteration is done, dpRow holds the LCS lengths for all prefixes of text2 relative to text1[0..i-1].

Final Result

After processing all characters of text1, the final LCS length is stored in dpRow[n].

Invariant

After completing the updates for text1[i-1], every dpRow[j] represents the LCS length of text1[0..i-1] and text2[0..j-1]. When all iterations finish, dpRow[n] gives the final answer.

Time Complexity

O(m × n) We perform a comparison for every pair of characters of text1 and text2), resulting in m × n total iterations, where m = text1.length and n = text2.length

Space Complexity

O(min(m, n)) Only one row of size min(m, n) + 1 is maintained at a time where m = text1.length and n = text2.length

Input-1

Input-2

Longest Common Subsequence - JS Solution Space Optimized

Solution code

Solution explanation

Solution explanation

Approach

Approach (Space-Optimized Dynamic Programming)

Iteration Logic

Variables Used During Each Update

Transition Rules

Row Processing Flow

Final Result

Invariant

Time Complexity

Space Complexity