Longest Common Subsequence
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return the length of the longest subsequence common to two strings (letters in order, not necessarily next to each other).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What is the answer when one string is empty?
- Hint 2When the last letters match, is it always right to use them together?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two playlists; you want the longest list of songs that appear in both in the same order. Make a table where the cell for (first x songs of playlist A, first y songs of playlist B) holds the longest common order so far. If song x of A equals song y of B, it extends the answer from (x - 1, y - 1) by one. Otherwise take the better of dropping the last song of A or the last song of B.
- The obvious way
Try all subsequences of one string and test in the other: O(2^n x m).
- The key insight
table[a][b] = longest common subsequence of the first a letters of text1 and first b letters of text2; the first row and column are 0. If the (a)-th letter of text1 equals the (b)-th of text2: table[a][b] = table[a - 1][b - 1] + 1; else max(table[a - 1][b], table[a][b - 1]). Answer table[len1][len2].
- The algorithm
- Table of zeros, one extra row and column.
- Equal letters: diagonal value + 1.
- Different letters: max of the cell above and the cell to the left.
- Return the bottom-right cell.
Watch it run
Exampletext1 = "abcde", text2 = "ace"
"a" is in both: common length 1.
length 1
Where people slip
- A subsequence is not a substring: letters need not be adjacent.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def longest_common_subsequence(text1, text2):
table = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)] # best for the first a / first b letters
for first_count in range(1, len(text1) + 1):
for second_count in range(1, len(text2) + 1):
if text1[first_count - 1] == text2[second_count - 1]:
table[first_count][second_count] = table[first_count - 1][second_count - 1] + 1
else:
table[first_count][second_count] = max(table[first_count - 1][second_count],
table[first_count][second_count - 1])
return table[len(text1)][len(text2)]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.