Loading page…
Practice problem · easy
A build system records each run as a log, one letter for every step it performed: a for fetch, b for compile, and so on. A dashboard compares two runs. It shows how many steps both runs performed in the same order, even when other steps happened in between.
Your team lead asks: "What is the longest list of steps that both logs contain, in the same order?"
Write longest_common_steps(first, second).
first and second are logs, strings of lowercase letters.Input: first = "abcb", second = "bcab"
Output: 3Let common[i][j] be the length of the longest common subsequence of the first i letters of first and the first j letters of second. With no letters on one side the answer is 0. When the next two letters match, the match extends the answer for both shorter logs: common[i][j] = common[i - 1][j - 1] + 1. When they differ, one of them is left out: common[i][j] = max(common[i - 1][j], common[i][j - 1]).
| (none) | b | c | a | b | |
|---|---|---|---|---|---|
| (none) | 0 | 0 | 0 | 0 | 0 |
| a | 0 | 0 | 0 | 1 (a matches a) | 1 (left 1) |
| b | 0 | 1 (b matches b) | 1 (left 1) | 1 (above 1, left 1) | 2 (b matches b: diagonal 1 + 1) |
| c | 0 | 1 (above 1) | 2 (c matches c: diagonal 1 + 1) | 2 (left 2) | 2 (above 2, left 2) |
| b | 0 | 1 (b matches b: diagonal 0 + 1) | 2 (above 2) | 2 (above 2, left 2) | 3 (b matches b: diagonal 2 + 1) |
The bottom right cell holds 3. The common subsequence is b, c, b.
Input: first = "abc", second = "xyz"
Output: 0The two logs share no letter.
Input: first = "axbxc", second = "abc"
Output: 3The second log is a subsequence of the first, because the two letters x can be skipped.
1 ≤ len(first) ≤ 1000 and 1 ≤ len(second) ≤ 1000Each log has up to 1,000 letters, so there are 1,000 × 1,000 = 1,000,000 pairs of positions. The number of ways to choose letters to keep from each log is far larger, so trying every pair of choices never finishes. A table with one entry for each pair of positions costs about a million small steps.
longest_common_steps · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.