LeetCode 1143: Longest Common Subsequence asks:
Given two strings, return the length of their longest common subsequence.
As we saw when solving the Longest Increasing Subsequence problem, a subsequence is formed by selecting elements from the input, with the only restriction being that they remain in their original order. For the LCS problem, if our two input strings are text1
and text2
, we can make a common subsequence using these steps: Iterate through text1
in order. For each character, either select it or don’t select it. When we get to the end of text1
, we’ll have a subsequence made up of characters from text1
. Then iterate through text2
and look for those same characters, in the same order. If we can find them all, we have found a common subsequence. We need to find the longest such subsequence.