Solving the Longest Common Subsequence with Dynamic Programming
When two strings share a hidden pattern, finding it by hand feels like detective work. The longest common subsequence problem turns that intuition into a precise algorithmic challenge, asking for the longest sequence of characters that appears in both strings while preserving their original relative order. Dynamic programming offers a remarkably elegant way to crack it, breaking the problem into smaller overlapping pieces that can be solved once and reused.
Programmers encounter this technique everywhere from Git's diff engine to DNA sequence alignment tools used in bioinformatics labs. Understanding how to apply dynamic programming to the longest common subsequence builds a foundation that transfers to knapsack problems, edit distance calculations, and many other optimisation puzzles. The patterns you learn here will sharpen your approach to interview questions and production code alike.
In Australia, computer science students at the University of Melbourne and UNSW Sydney tackle this exact problem during their second-year algorithms courses. Local software teams at firms like Canva and Atlassian rely on similar subsequence-matching logic for features ranging from plagiarism detection to collaborative editing. Walking through the solution step by step gives you a tool that resonates with both academic theory and the practical work happening across Sydney, Melbourne, and Brisbane.
Grasping the problem itself
The longest common subsequence, often abbreviated LCS, compares two sequences and returns the longest subsequence that can be derived from both by deleting some elements. The key word is subsequence rather than substring: the matching characters do not need to sit contiguously in the original strings, only in the same relative order. For example, given the strings "ABCBDAB" and "BDCAB", one valid longest common subsequence is "BCAB" with a length of four.
This subtle distinction between subsequence and substring trips up many learners. A substring must be continuous, like the "CAB" sitting together inside "ABCBDAB". A subsequence can skip characters, so "BDB" also counts as a valid shared pattern even though the letters are scattered. Recognising this difference matters when you move from the abstract definition to concrete code, because the algorithm you choose depends entirely on which constraint you enforce.
The applications stretch far beyond textbook exercises. Bioinformatics researchers in Melbourne and Sydney use LCS variants to compare genetic sequences, looking for conserved regions across species. Version control systems such as Git rely on similar logic to highlight changes between file revisions. Even search engines employ subsequence matching to catch typos and suggest corrections, making the algorithm a quiet workhorse behind tools you use every day. Readers who want a broader tour of related dynamic programming topics can explore hello ML for tutorials on edit distance, knapsack variants, and more.
Starting from a recursive intuition
Before reaching for dynamic programming, it helps to feel the natural recursion hiding inside the problem. Consider two strings, X and Y. If their last characters match, the longest common subsequence must include that character, followed by the longest common subsequence of the two prefixes that exclude those last characters. If the last characters differ, you must try two options: drop the last character of X while keeping Y intact, or drop the last character of Y while keeping X intact, then take whichever option yields a longer result.
This recursive definition feels clean, yet it carries a hidden cost. The same subproblems appear repeatedly. For instance, computing the LCS of "ABC" and "BAC" might evaluate the LCS of "AB" and "BA" twice, once from each branch of the recursion tree. With strings of length m and n, the naive approach runs in exponential time, which quickly becomes impractical. A typical bioinformatics dataset in a lab at the University of Queensland could involve sequences thousands of characters long, rendering the brute-force method useless.
The overlapping structure is the classic signal that dynamic programming can help. By storing the answer to each subproblem in a table and looking it up when needed, you collapse the exponential explosion into a polynomial march. This shift from recomputation to memorisation is the conceptual heart of the technique, and it applies whether you use top-down memoisation or bottom-up tabulation. Both approaches reach the same destination, simply by different routes.
Filling the dynamic programming table
The bottom-up approach builds a two-dimensional grid where cell dp[i][j] holds the length of the longest common subsequence for the first i characters of X and the first j characters of Y. The table starts with a row and column of zeros, representing the base case that an empty string shares no subsequence with anything. From there, you work outward, one row and column at a time, filling each cell based on a simple rule derived from the recursive definition.
If the i-th character of X matches the j-th character of Y, the value dp[i][j] equals dp[i-1][j-1] plus one, because you can extend the subsequence by that matching character. If the characters differ, dp[i][j] takes the maximum of dp[i-1][j] and dp[i][j-1], reflecting the choice to skip either the last character of X or the last character of Y. Walking through the strings "ABCBDAB" and "BDCAB" on paper makes the pattern visible: the bottom-right cell ends up holding the length of the longest common subsequence, which is four.
Pseudocode for the core loop looks straightforward. You iterate i from one to the length of X, and within that loop you iterate j from one to the length of Y. Each iteration performs a constant number of operations, so the total running time is O(m times n) and the memory consumption is also O(m times n). For a coding interview at a Sydney fintech or a technical test at the Australian Digital Health Agency, this complexity bound is exactly what you want to be able to quote from memory.
Reconstructing the actual subsequence
Knowing the length is often not enough. Many real applications, such as displaying diff results or printing aligned DNA sequences, require the actual subsequence string. Luckily, the table you just filled contains enough information to recover it. Starting from the bottom-right cell, you walk backwards through the grid, making the same decisions in reverse.
When the characters at position i in X and j in Y match, that character is part of the answer. You prepend it to your result and move diagonally up and left to cell dp[i-1][j-1]. When the characters differ, you move to whichever neighbour holds the larger value, up or left, and continue. If both neighbours hold equal values, either direction works, though you usually prefer moving up to keep the reconstruction deterministic. Reaching the top row or leftmost column signals the end of the trace.
This backtracking adds only O(m plus n) extra work on top of the table construction, since you traverse at most m plus n steps. Students preparing for technical interviews at companies like Seek in Melbourne or SafetyCulture in Sydney often practise this step carefully, because reconstructing the answer tests a deeper understanding than merely counting it. A common pitfall is forgetting to handle the case where both moves are valid, which can lead to different valid subsequences depending on the path taken.
Streamlining memory and comparing approaches
The O(m times n) memory footprint becomes a concern when dealing with very long strings, such as comparing two versions of a large codebase or aligning lengthy genomic sequences. A clever observation saves the day: filling each row of the table only requires the previous row. Storing two rows at a time reduces the memory to O(min(m, n)), which can be compressed further into a single rolling array if you only need the length.
This space optimisation is a classic interview follow-up, and it illustrates a broader principle in dynamic programming. Whenever your recurrence only looks back a fixed number of steps, you can trade memory for time or vice versa. For the longest common subsequence, the trade-off is particularly favourable: you can halve the memory with negligible impact on readability, and you can compress it even further at the cost of slightly more complex indexing.
Different approaches suit different contexts, as the comparison below illustrates.
| Approach | Time Complexity | Space Complexity | Reconstructs Sequence | Typical Use Case |
|---|---|---|---|---|
| Naive Recursion | O(2^min(m,n)) | O(min(m,n)) | Yes | Teaching only, too slow in practice |
| Top-Down Memoisation | O(m · n) | O(m · n) | Yes | When recursion feels natural |
| Bottom-Up Tabulation | O(m · n) | O(m · n) | Yes | Most common interview solution |
| Space-Optimised DP | O(m · n) | O(min(m, n)) | No (length only) | Length-only queries on huge inputs |
| Hirschberg's Algorithm | O(m · n) | O(min(m, n)) | Yes | Memory-constrained reconstruction |
For personalised feedback or to suggest a follow-up topic, feel free to contact the editorial team through the site. With this foundation, the algorithm applies equally well to technical interviews in Perth and production systems running in Adelaide, and the bottom-right cell of your table holds the answer you need.