The Longest Common Subsequence (LCS) Problem

When you are solving a Dynamic Problem algorithm, you are likely to face the Longest Common Subsequence (LCS) Problem. 

Then, what is LCS?

A typical problem of LCS is like this:

"Given two sequences, find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order but is not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. "

LCS example

In order to solve this problem, you need to use a 2-dimensional array to keep track of the longest common sequence of the given position. 

What you have to do is create i and j that will loop upward to each of the two strings.

One important assumption to make is that if a character at a position at the end of the first string is equal to a character at a position at the end of the second string, then it is always better to take them as an element of LCS.

For example, if given two strings "abeda" and "cbeea" end with a character "a", then picking that "a" at the last position is always good. 

Based on this assumption, the longest LCS at the position i and j is 1 character longer than i-1 and j -1 position if the two characters at i and j position are the same. 

If it is not, the longest LCS at i and j position is which is the largest between i -1 and j position and i and j -1 position of the first and the second string. 

Simply, if the 2-D array (iSaveLCSValArray[i][j]) that saves the longest LCS at the given position i and j, 

iSaveLCSValArray[i][j] = (iSaveLCSValArray[i-1][j-1] +1): 

if the two characters at i and j position are the same. 

Otherwise, iSaveLCSValArray[i][j] = Maximum between (iSaveLCSValArray[i][j-1], iSaveLCSValArray[i-1][j]).

Here is a simple code implementation of LCS problem. 

 

void LCS() {

for (int i = 1; i <= sFirst.size(); i++) {

for (int j = 1; j <= sSecond.size(); j++) {

if (sFirst[i-1] == sSecond[j-1]) {iSaveLCSValArray[i][j] = iSaveList[i - 1][j - 1]                         + 1;}

else {iSaveLCSValArray[i][j] = max(iSaveLCSValArray[i][j - 1],                                                     iSaveLCSValArray[i-1][j]);}

}

}

}

References :

https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

GitHub:

https://github.com/AdvancedUno/AlgorithmProblems/tree/main/Backtrack_Shortest_Path/LCS