Longest Common Subsequence
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
Two ancient scrolls each carry a line of runes, written left to right.
Find the length of the longest sequence of runes that shows up on both scrolls in the same relative order. The matching runes don't need to sit next to each other on either scroll, and nothing needs to line up in position, only the order has to agree.
Input: a = "abc", b = "acb"
Output: 2
"ab" appears in order on both scrolls (a then b), and so does "ac" (a then c). No sequence of 3 runes appears in order on both.
Input: a = "aaaa", b = "aa"
Output: 2
The second scroll only has two runes total, so the longest shared sequence can be at most 2 runes long, and "aa" does appear in order on the first scroll too.
Input: a = "abcdefgh", b = "ijklmnop"
Output: 0
The two scrolls share no runes at all, so the longest common sequence is empty.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.