LCS: Longest Common Subsequence

One of the popular problems that we come across in the interviews or while learning about dynamic programming is the longest common subsequence or LCS. There are multiple approaches to solve this problem and we will look at both the approaches in this post.

To begin with, let us have 2 strings or char arrays that contains the sequence of characters that are to be compared.