The longest common subsequence problem is the problem of finding the longest subsequence common to all sequences in a set of sequences. It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

Objective: Given two string sequences, write an algorithm to find the length of longest subsequence present in both of them.

These kind of dynamic programming questions are very famous in the interviews like Amazon, Microsoft, Oracle and many more.

What is Longest Common Subsequence: A longest subsequence is a sequence that appears in the same relative order, but not necessarily contiguous(not substring) in both the string.

String A = "acbaed";

String B = "abcadf";

Longest Common Subsequence(LCS):     acad, Length:4

Approach:

Recursion:

Start comparing strings in reverse order one character at a time.

Now we have 2 cases –

1. Both characters are same

1. add 1 to the result and remove the last character from both the strings and make recursive call to the modified strings.

2. Both characters are different

1. Remove the last character of String 1 and make a recursive call and remove the last character from String 2 and make a recursive and then return the max from returns of both recursive calls. see example below

Case 1:

String A: "ABCD", String B: "AEBD"

LCS("ABCD", "AEBD") = 1 + LCS("ABC", "AEB")

Case 2:

String A: "ABCDE", String B: "AEBDF"

LCS("ABCDE", "AEBDF") = Max(LCS("ABCDE", "AEBD"),

LCS("ABCD", "AEBDF"))