How do you find the longest common subsequence? | Interview Question

Q: How do you find the longest common subsequence?

**Target Audience:** Beginners preparing for coding interviews — you need loops, lists and 2D lists. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Two friends each wrote down the films they watched this year, in the order they watched them. Maya's list is *Alien, Barbie, Cars, Dune, Elf*; Raj's list is *Alien, Cars, Elf*. They want to know: **what is the longest run of films they both watched in the same order?** Not necessarily back to back — Maya watched Barbie in between — but in the same order. The answer is *Alien, Cars, Elf*, three films. That q

The problem

Question presented to candidate: "Given two strings, return the length of their longest common subsequence — characters in the same order, but not necessarily next to each other. Then show me how you would get the subsequence itself. Please code it in Python."

What a strong answer should cover:

The state dp[i][j] = LCS length of the first i characters of one string and the first j of the other, with row 0 and column 0 meaning the empty prefix.
The recurrence: equal last characters → dp[i-1][j-1] + 1; different → max(dp[i-1][j], dp[i][j-1]); and why the order of filling makes every input ready.
O(m·n) time and space, and the two-row version in O(min(m, n)) space when only the length is needed.
Rebuilding the string by walking back from dp[m][n], and noting that ties mean the LCS is not unique.
Python details: building rows with a list comprehension (not [[0] * n] * m, which aliases one row), and that a memoized recursive version hits the default recursion limit of 1000 on long strings.

Clarifying questions expected:

Do you need the length only, or the subsequence string as well?
Subsequence (gaps allowed) or substring (contiguous)?
How long can the strings get?

Code / implementation expected: Yes — a bottom-up table in Python returning the length, plus a walk back that returns one LCS string.

dp
lcs

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you need loops, lists and 2D lists.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Two friends each wrote down the films they watched this year, in the order they watched them. Maya's list is Alien, Barbie, Cars, Dune, Elf; Raj's list is Alien, Cars, Elf. They want to know: what is the longest run of films they both watched in the same order? Not necessarily back to back — Maya watch

The solution is hidden so you can try first

15 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonLCS table, length and one LCS string on six pairs

Practice

PythonNaive recursion vs memo vs table vs two rows

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.