Longest Common Subsequence (LCS) DP Problem

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

If we had 2 strings “abc” and “ac” the LCS will be “ac” . We get to this LCS by looking at the last letter of both strings. So, first, we compare ‘c’ from “abc” and ‘c’ from “ac”, these two characters are equal so we can add it to the end of our LCS.

Now we are left with “ab” and “a”, we will now compare ‘b’ from “ab” and ‘a’ from “a”, but these two are not equal so, we will remove first check if we remove ‘a’ from “a” we are left with “”(empty string) and the LCS between “” and “ab” will be “”.

So, we will now instead of removing “a” we will remove ‘b’ from “ab” and compare with “a” , after removing ‘b’ we are left with “a” from “ab” and the other string is already “a”, both characters are equal so we can append “a” before “c” (i.e. “ac”) in our LCS.

So, the logic here is, whenever we are finding LCS between two strings, we look at the final character and we say are these final characters of each of these strings are equal? if they are equal, then we get the…