Two people's edit logs are recorded as strings of action codes, one letter per action. Write a function that returns the length of the longest sequence of actions that appears in both logs in the same order. The actions don't have to be next to each other: you can skip actions in either log.
text
1longest_shared("ABCBDAB", "BDCABA") -> 4
2longest_shared("AXY", "AYX") -> 2
3longest_shared("ABC", "DEF") -> 0
In the first example, "BCBA" appears in both in order (so do "BDAB" and "BCAB").
Write longest_shared(a, b) in Python or longestShared(a, b) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 22 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Look at the last letters
Compare the last letter of a with the last letter of b. If they're equal, that letter can end the shared sequence: the answer is 1 plus the answer for both strings without their last letters. If they're different, at least one of them isn't used, so the answer is the better of dropping the last letter of a or dropping the last letter of b.
Step 2
Define the state
Let L[i][j] be the answer for the first i letters of a and the first j letters of b. The final answer is L[len(a)][len(b)], and L[0][j] = L[i][0] = 0 (an empty log shares nothing).
Filling rows in order means every value you need is ready. Each row only reads the row above it, so you can keep just two rows, cutting memory from O(n × m) to O(m).
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Build the table row by row with the recurrence above, keeping only the previous row and the current one. Return the last value of the final row.
python
1def longest_shared(a, b):
2 prev = [0] * (len(b) + 1) # row i-1 of the table
↑the row above (first i − 1 letters of a)
3 for i in range(1, len(a) + 1):
4 row = [0] * (len(b) + 1)
5 for j in range(1, len(b) + 1):
6 if a[i - 1] == b[j - 1]:
↑last letters match
7 row[j] = prev[j - 1] + 1
↑1 + the diagonal
8 else:
9 row[j] = max(prev[j], row[j - 1])
↑drop a letter from one side
10 prev = row
11 return prev[len(b)]
javascript
1function longestShared(a, b) {
2 let prev = new Array(b.length + 1).fill(0) // row i-1 of the table
O(n × m) time for strings of lengths n and m. O(m) space with two rows (O(n × m) if you keep the whole table, which you'd need to rebuild the sequence itself).
What we learned
Two-sequence problems: the state is a pair of prefix lengths (i, j).
Decide based on the last characters: match, or drop one from either side.
Space can drop to two rows when each row only depends on the previous one.