Longest Common Subsequence

Find the longest sequence of characters that appears in two strings in the same order. Characters do not need to be next to each other.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Longest Common Subsequence: Fill prefix states left to right: a match takes diagonal + 1; a mismatch takes max(left, up).

Input and goalFind the longest sequence of characters that appears in two strings in the same order. Characters do not need to be next to each other.

Initialize empty-prefix answersFor first = "abc" and second = "ac", an empty prefix has LCS length 0 with every other prefix.

0base000??0??0??

columnsempty, a, crowAxisempty, a, b, c

Recognize it

Use it when two sequences must retain relative order while allowing skips, and the answer for two prefixes depends only on shorter prefixes of one or both sequences.

Keep true

After writing current[index], it is the LCS length for the processed first-string prefix and second[:index]; previous holds the complete answers for the prior first-string prefix.

Reuse it

For ordered matching problems, define a state on two prefixes; matching endpoints consume both, while mismatching endpoints branch by skipping one side and combining optimal smaller states.

Pattern: Two-dimensional DP stored as two rows.

State: The best answer for two string prefixes.

Simple idea: Matching characters add one to the answer before both characters. Different characters skip one character from either string and keep the better result.

def longest_common_subsequence(first: str, second: str) -> int:
   previous = [0] * (len(second) + 1)

   for first_char in first:
      current = [0]
      for index, second_char in enumerate(second, 1):
         if first_char == second_char:
            current.append(1 + previous[index - 1])
         else:
            current.append(max(current[-1], previous[index]))
      previous = current

   return previous[-1]

Cost: $O(mn)$ time and $O(n)$ space.