ALGORITHM READING NOTE

Longest Common Subsequence

LCS finds the longest sequence of values that appears in both inputs in the same relative order, but not necessarily contiguously.

TYPEAlgorithmCATEGORYSets & Dynamic ProgrammingDEPTHAdvancedTYPICAL COMPLEXITYO(mn)

SHORT INTERVIEW ANSWER

Start with this mental model

LCS finds the longest sequence of values that appears in both inputs in the same relative order, but not necessarily contiguously.

SIMPLE EXPLANATION

How it works, without unnecessary jargon

dp[i][j] usually means LCS length for prefixes ending before i and j.

Matching characters extend the diagonal state; otherwise take the best of dropping one side.

EXECUTION

Read the algorithm as a sequence of decisions

Define the state precisely.

Write the transition/choice from smaller states.

Set base cases, then decide memoization, tabulation or backtracking.

A small example to keep in mind

Read a tiny input by hand and write down the state after every important operation. For Longest Common Subsequence, the goal is to make the invariant visible rather than to memorize code.

READABLE JAVASCRIPT IMPLEMENTATIONJavaScript

function lcs(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => Array(b.length + 1).fill(0));
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[a.length][b.length];
}

How to read this code

Do not memorize the syntax. Follow the state that changes on each line and connect it to the invariant described above.

COMPLEXITY

O(mn)

Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.

WHEN TO USE IT

Good fit

Use DP when subproblems overlap and optimal solutions can be composed from smaller optimal states.

COMMON MISTAKES

What usually goes wrong

Writing recurrence before defining state.
Using DP when state space is larger than the original problem.

HOW TO EXPLAIN IT IN AN INTERVIEW

A professional answer shape

Explicitly distinguish subsequence from substring. This is one of the most common interview confusions.

Problem→Core idea→Invariant / state→Big-O→Trade-off

QUICK INTERVIEW CHECK

What problem does Longest Common Subsequence solve?

LCS finds the longest sequence of values that appears in both inputs in the same relative order, but not necessarily contiguously.

What should I mention about complexity?

Its typical cost here is O(mn), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.

What is the most common mistake?

Writing recurrence before defining state.

Continue readingMemoizationTabulationBacktracking

function lcs(a, b) { const dp = Array.from({ length: a.length + 1 }, () => Array(b.length + 1).fill(0)); for (let i = 1; i <= a.length; i++) { for (let j = 1; j <= b.length; j++) { dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]); } } return dp[a.length][b.length]; }