Longest Common Subsequence (LCS) DP Problem

Shaila Nasrin
4 min readAug 1, 2019

A subsequence is a group of characters that appears sequentially but it doesn’t have to be contiguous though it can be. For example s = “AFPKL” in this string valid sub-sequences can be “AFP”, “APK”, “AFKL” etc.

So, the problem is asking us to return the sequence of the longest common subsequence (LCS) between two strings. For instance:

Input: “abdez”, “bxide”

Output: [“b”, “d”, “e”]

Solution Approach