Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Longest Common Subsequence

Longest Common Subsequence explained: build the 2D DP table cell by cell, recover the LCS string, O(m·n) tested Python and a live table-filling visual.

Also searched as: LCS dynamic programming · longest common subsequence dp table · LCS of two strings

🧮

Try it live Free

2D DP Table: LCS & Edit Distance

Type two strings, pick LCS, and watch the table fill cell by cell with arrows showing which neighbour won, then trace the answer path back out of the grid while the counter compares naive recursion's call count with the m×n cells.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

Given two strings, return the length of their longest common subsequence: the longest sequence of characters that appears in both strings in the same order, though not necessarily next to each other.

Inputa = "abcde", b = "ace"
Output3

"ace"

Inputa = "abc", b = "def"
Output0

The key insight

Compare the last characters of two prefixes. If they match, that character extends the LCS of both shorter prefixes: dp[i-1][j-1] + 1. If they differ, one of them is not in the answer, so take the better of dropping either: max(dp[i-1][j], dp[i][j-1]). A table of all prefix pairs holds every subproblem exactly once.

Brute force first: Generating all 2m subsequences of one string and checking each against the other is exponential.

Step-by-step approach

  1. Create a (m + 1) × (n + 1) table of zeros; row 0 and column 0 represent empty prefixes.
  2. For i in 1..m and j in 1..n, compare a[i-1] and b[j-1].
  3. On a match, dp[i][j] = dp[i-1][j-1] + 1 (diagonal).
  4. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (up or left).
  5. The answer is dp[m][n]. To recover the string, walk back from that cell following the moves that produced each value.

Python solution

PYTHON 3tested
def longest_common_subsequence(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1          # diagonal
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # up or left
    return dp[m][n]

Complexity

TimeO(m · n)
SpaceO(m · n)

One O(1) computation per cell of the m × n table. Only the previous row is needed for the length, so space can drop to O(min(m, n)).

Common mistakes

Frequently asked questions

What is the time and space complexity of LCS?

O(m × n) time. The full table is O(m × n) space; if you only need the length, two rows give O(min(m, n)) space.

How do I print the actual longest common subsequence?

Keep the full table and start at dp[m][n]. If the characters match, record it and move diagonally; otherwise move to whichever of up or left holds the larger value. Reverse the collected characters at the end.

What is the difference between LCS and edit distance?

Both fill a table over prefix pairs. LCS maximises matched characters; edit distance minimises insertions, deletions and replacements. With only insertions and deletions allowed, the edit distance equals m + n - 2 × LCS.

Where is LCS used in practice?

Diff tools such as git diff, DNA sequence comparison and plagiarism checks all rely on LCS-style alignment.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.