Where it runs
1. The problem
The previous step looked for the longest increasing chain inside one list. Now there are two lists. You want the longest chain of items that appears in both lists in the same order.
The items don't have to sit next to each other; skipping is allowed. You keep only the items found in both sequences, and you keep their order.
Take the words "ABCBDAB" and "BDCAB". The longest thing in both, in order, is "BCAB", length 4. Skips are allowed, so B, C, A and B can be taken from places far apart, as long as the order holds.
That is what git diff does inside. It takes two versions of a file and finds the longest set of lines that stayed the same and come in the same order. Everything else it shows as changes.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- longest increasing subsequence
- longest common subsequence between two strings
- minimum edits to turn one string into another
- keep relative order, may skip items
- diff or alignment between two sequences
Looks similar, isn't
- Dynamic programming (1-D)
One index is enough there. Comparing two sequences needs two of them.
- DP on strings (word break)
That page splits a single string into pieces. This one lines two sequences up.
- Binary search (array)
The n log n form of increasing subsequence uses binary search. The table form is the slower one.
- Two pointers (same direction)
Checking whether one string is a subsequence needs no table. Finding the longest common one does.
One sequence of n items costs O(n²) time. Two sequences of n and m cost O(nm), and one kept row is enough.
On LeetCode
Problems on two strings or arrays that keep their common part in order, such as the fewest deletions to make them equal or the shortest string that holds both. The cell for i and j comes from three neighbours, and a match takes the diagonal.
The lesson task, word for word.
Lines that do not cross connect equal numbers in the same order, so the answer is the longest common subsequence of the two arrays.
Everything outside the common part gets deleted, so the answer is both lengths added up minus twice the common length.
Fill the table, then walk back from the corner and write each shared letter once and every other letter as you pass it.