Motivation
Two strings may share an ordered pattern even when its symbols are not adjacent. Finding the longest such pattern is useful whenever relative order matters but gaps are allowed. A direct search over all subsequences can revisit the same prefix questions many times. Dynamic programming records the best answer for each pair of prefixes, then uses those answers to build an optimal subsequence.
A subsequence differs from a substring: deleting symbols is permitted without requiring the retained symbols to remain consecutive in the original string. The order of the retained symbols must nevertheless be preserved. These notes compute a length and one witness; finding all witnesses is a different output problem.
Definitions
Definition 2.1.1
(Subsequences and the prefix table)
Let and be finite strings. A string is a subsequence of if it can be obtained by deleting zero or more positions from without changing the order of the remaining positions. Repeated symbols are allowed, but a selected position cannot be used twice. A common subsequence is a subsequence of both strings. The empty string is always common, including when either input is empty.
For and , define as the maximum length of a common subsequence of prefixes and . Empty prefixes give . The state records both prefix lengths because removing a last character from one string changes only one of the two constraints.
Theorems
Theorem 2.1.2
(Prefix recurrence)
For ,
The table value is the length of a longest common subsequence.
Theorem 2.1.3
(Computation and reconstruction)
Filling the table in an order in which the top, left and diagonal predecessor entries are already known takes time and space (or when both lengths are positive). Starting at , follow a diagonal and record the symbol when the last symbols agree; otherwise follow a predecessor with the larger table value, breaking ties arbitrarily. Reversing the recorded symbols gives a longest common subsequence.
Proof sketch or proof idea
Proof
(The prefix recurrence and reconstruction)
If , append to any optimal common subsequence of the two shorter prefixes. This gives a common subsequence of length . Conversely, take any optimal common subsequence of the longer prefixes. If it uses either last position, its final symbol is ; the matching occurrence in the other string can be moved to that string's last position, leaving a common subsequence of the two shorter prefixes before it. If it uses neither last position, appending would produce a longer common subsequence, contradicting optimality. Hence an optimum has a representation using both last positions, and removing its last symbol gives a common subsequence of the shorter prefixes. The two inequalities prove the equal-symbol case.
If , no common subsequence can use both last positions as a matched pair. Every common subsequence therefore avoids at least one of them: if it used both in separate matched positions, their relative order would force the last selected symbols in the two strings to be equal. It belongs to at least one of the two smaller-prefix subproblems. Conversely, a common subsequence of either smaller pair is also common to the original prefixes. Taking the maximum proves the unequal-symbol case.
By induction on , the boundary values and recurrence compute every table entry correctly. During reconstruction, a diagonal move in the equal case removes one symbol from an optimal witness, while an unequal-case move keeps the optimum length. Each move decreases at least one index, so the process terminates at a boundary. The symbols are discovered from right to left and must be reversed. Their recorded positions are increasing after reversal, so they form a common subsequence of the claimed optimal length.
Proof X-ray
A valid witness and an upper bound
Appending a matched symbol supplies a candidate, but does not by itself prove optimality. The converse argument must show that an optimum can be represented using both last positions, so its prefix cannot exceed the best shorter-prefix value.
The unequal case closes differently. A common subsequence that uses the last position of must end with , and one that uses the last position of must end with . Using both would force , so the hypothesis excludes it, and every common subsequence already lives in one of the two smaller problems.
Worked examples
Worked example 2.1.4
(Gaps are allowed)
For and , the string is common: delete from the first input and delete nothing from the second. No common subsequence can exceed the length of the second input, so the optimum length is two. The same witness is not a substring of .
Worked example 2.1.5
(A tie gives different witnesses)
For and , both and are common subsequences of length one. A length-two common subsequence would have to equal both input strings, which it cannot. At the final unequal pair the two predecessor entries tie; either choice reconstructs an optimum, but the chosen witness may differ.
Worked example 2.1.6
(Repeated symbols use positions)
For and , and are both common subsequences of length two. The full strings differ, so there is no common subsequence of length three. A valid witness uses the first two positions of and positions one and three of ; it does not reuse one occurrence.
Common mistakes
Counterexample mode
A shared substring is a different problem
For and , the longest common subsequence has length two, but no common substring of length two exists. Replacing the subsequence recurrence with a substring recurrence silently changes the problem.
Common mistake
(Reading the length table as the answer)
A length table does not itself display the witness. If the task asks for one subsequence, follow and record the choices. If it asks for every longest subsequence, arbitrary tie breaking is insufficient. Distinct paths through a table can also spell the same subsequence, especially when symbols repeat.
Filling and reading a table
Initialize row zero and column zero to zero. Then process rows and, within each row, columns . The entries above, to the left and diagonally above-left are available when needed. This order is one valid topological order of the dependency graph; a column-first order also works. The cells represent prefix lengths, not character indices alone, so row zero is a real boundary even though there is no character .
Worked example 2.1.7
(A small table and trace)
Take and . Including empty prefixes, the table rows are
At the last cell the two symbols are both , so record and move diagonally to the cell for and . There the symbols agree, so record and move diagonally to a boundary. Reversing the recorded sequence yields , a common subsequence of length two. The table certifies that no longer common subsequence exists.
A worked table is also a diagnostic tool. Every entry is between zero and the smaller prefix length. Values cannot decrease when either prefix is extended, because all previous common subsequences remain available. If an implementation produces a smaller value after adding a character, it has violated this monotonicity. These checks can expose an error but do not replace the recurrence proof: an incorrect table can satisfy both bounds and monotonicity.
Why the equal-symbol case is safe
Common mistake
(Assuming every optimum uses both last positions)
The equal-symbol recurrence is sometimes justified too quickly by saying that every optimum must already use both last positions. An optimum as a sequence of positions need not do so when symbols repeat. For example, with and , the first of can be used in an optimal match, leaving the final unused. What the proof needs is weaker: there exists an optimal representation using both last positions. Moving a matched final occurrence to a later equal occurrence preserves all earlier order relations.
This distinction between a string and its position witnesses matters in reconstruction. Different sets of matched positions can produce the same symbol sequence. If the goal is one common subsequence, any valid matching positions suffice. If the goal is to count distinct strings, summing path counts is generally wrong because several paths may spell the same string. If the goal is instead to count position matchings, that is a different, explicitly specified counting problem.
The unequal-symbol proof also uses positions, not merely character membership. A symbol can appear in both strings many times, but the last selected position in one string must match the last selected position in the other. If a common subsequence used both final positions, those positions would represent the same final selected symbol. Since the final symbols differ, this is impossible. Therefore at least one final position is unused and can be removed without losing that witness.
Concept lensCombinatorial
Longest common subsequence as insertion-deletion distance
Transform into using only insertions and deletions. The symbols of that are never deleted form a common subsequence of and , and every common subsequence gives such a script: delete the other symbols of , then insert the other symbols of . The least number of operations is therefore . For and this is .
Space and output choices
The full table uses one cell for every pair of prefixes. If only the optimum length is needed, each row depends on the preceding row and its own previous cell, so two rows suffice. This reduces storage to cells when rows correspond to prefixes of ; swapping the strings can make the shorter dimension the stored row. The boundary row must be initialized correctly and the current row's left value must be retained. The time bound remains proportional to the number of cells.
A two-row computation by itself does not retain all the predecessor choices for the simple backward trace. It is therefore incorrect to promise both that exact trace and two-row storage without explaining how the missing information is recovered. One can keep the full table, recompute portions, or use a separately justified divide-and-conquer reconstruction. The first option is the algorithm proved here. Output storage for the witness is also needed: a longest common subsequence can contain up to symbols.
The stated time counts table operations and assumes symbol equality can be tested in constant time. If input symbols are themselves large structures, their comparison cost must be included. The method works for any finite sequences with a well-defined equality test; the alphabet need not be small. It also handles an empty input directly through the initialized boundary, producing the empty witness without entering the reconstruction loop.
A strategy check
Counterexample mode
Matching the earliest occurrence is not optimal
One tempting greedy rule is to match each symbol of the first string to its earliest possible occurrence in the second whenever possible. For and , matching the initial to the last position of leaves no room for or , so this rule obtains length one. Skipping allows of length two. A local match can consume a position that blocks a better later pattern; the dynamic program compares alternatives on smaller prefix pairs instead of assuming the first available match is safe.
This counterexample concerns the stated greedy rule, not every algorithm that uses an earliest-occurrence data structure. A data structure can accelerate a correct algorithm without determining its objective. To justify a greedy rule generally, one would need a proof that its choice can be part of an optimum for every input. A single counterexample disproves that universal assertion, while the recurrence proof establishes correctness for every finite pair of inputs.
Summary
Prefix pairs give a finite state space. Matching last symbols reduce both prefixes; unequal last symbols force an optimal solution to avoid at least one of them. The resulting table computes the optimum length, and a backward trace recovers a witness.
Exercises
Quick check
(Find a longest common subsequence of and and justify its length.)
Solution · Answer
Both and are common subsequences of length two. Length three would require the full strings to be equal, so two is optimal.
Quick check
(What are the boundary values if is empty and has length five?)
Solution · Answer
Every entry for is zero: the empty string is the only subsequence of the empty input.
Quick check
(For and , why is the answer not two?)
Solution · Answer
The second input has only one position, so any of its subsequences has length at most one. The symbol is a common subsequence of length one.
Quick check
(For and , give the optimum length and one witness.)
Solution · Answer
The two strings have no common symbol. The maximum length is zero and the empty string is a witness.