Dynamic Programming: Longest Common Subsequence

You are given 2 strings, you need to find the longest common subsequece.

Input:

Str 1: abfgkl

Str 2: abcdel

Output: 3

Here we have “abl” as the longest common subsequence.

Here we are not finding the substring, so there can be gaps in between.

And you cannot change the relative order of the remaining characters.

We need to print the length of LCS.

There are multiple variations for this problem, we shall have a look at all the problems:

Largest Common Subsequence

Print LCS

Shortest Common Subsequence

Print SCS

Minimum number of insertion and deletion

Longest repeating subsequence

length of longest repeating subsequence of which is a substring

subsequence pattern matching

count how many times a appear as subsequence in b

longest palindromic subsequence

longest palindromic substring

count of palindromic substring

min num of deletion in a string to make it a palindrome

min num of insertion in a string to make it a palindrome

longest increasing subsequence

longest alternating subsequence

longest common subsequence

LCS (Longest Common Subsequence) of three strings

Maximum Sum Increasing Subsequence

Count all subsequences having product less than K

Longest subsequence such that difference between adjacent is one

Maximum subsequence sum such that no three are consecutive

we can solve this problem with the help of DP.

Before we start with DP, we shall first see the recursive approach and then we shall look at DP.

For any recursive problem to solve, we need to have 2 pointes:

1. Base Condition

2. Recursion/choice tree

Our base condition should be smallest valid input.

So in our case, smallest valid input will be an empty string.

So, if either of the strings are null, then we return zero.

In every step of recursion, we have a choice to make.

And that choice should somehow leads to smaller the input size.

In our example, we have 3 cases, if we start from the last character,

str 1: abc

str 2: bac

If both of the last characters matches, then we decrement the string size from both of the strings.

For that the code will be:

    if (str1[m-1] == str2[n-1])

        return 1 + lcs(str1, str2, m-1, n-1);

str 1: abc

str 2: bcd

Here “c” in first string is at the end, and “c” in second string is in the middle. So we need to decrement the second string, and keep the first string as it is.

Fot that the code will be:

lcs(X, Y, m, n-1)

str 1: bcd

str 2: abc

Here “c” in first string is in the middle, and “c” in second string is at the end. So we need to decrement the first string, and keep the second string as it is.

Fot that the code will be:

lcs(X, Y, m-1, n)

In the top down approach, as there are multiple sub problems, we can create a DP array that will hold the value of previously computed values.

As the input size increases, it will be difficlut to make recursive calls as we have limited stack size.

So we go with bottom up approach.

In this approach, we start from the base case and build the table upon it.

For every index, we have 2 choices:

1. If the character text[i] matches text[j], then increment the count, and then decrement the values.

2. If the character text1[i] does not match text2[j], we will take the longest subsequence by either skipping ith or jth character from the respective strings.

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

int recursion_util(string text1, string text2, int i, int j) {
      if (i >= text1.size() || j >= text2.size()) {
          return 0;
      }
      if (text1[i] == text2[j]) {
          return 1 + recursion_util(text1, text2, i + 1, j + 1);
      }
      return max(recursion_util(text1, text2, i + 1, j), recursion_util(text1, text2, i, j + 1));
  
}


int lcs_recursion(string text1, string text2) {
    return recursion_util(text1, text2, 0, 0);
}


int top_down_util(const string &text1, const string &text2, int i, int j, vector<vector<int>> &memo) {
    if (i >= text1.size() || j >= text2.size()) {
        return 0;
    }
    if (memo[i][j] == -1) {
        if (text1[i] == text2[j]) {
            memo[i][j] = 1 + top_down_util(text1, text2, i + 1, j + 1, memo);
        } else {
            memo[i][j] = max(top_down_util(text1, text2, i + 1, j, memo), top_down_util(text1, text2, i, j + 1, memo));
        }
    }
    return memo[i][j];
}

int lcs_top_down_dp(string text1, string text2) {
    vector<vector<int>> memo(text1.size(), vector<int>(text2.size(), -1));
    return top_down_util(text1, text2, 0, 0, memo);
}



int lcs_bottom_up(string text1, string text2) {
    vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
    for (int i = 1; i <= text1.size(); ++i) {
        for (int j = 1; j <= text2.size(); ++j) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[text1.size()][text2.size()];
}


int main()
{   
    string str1 = "abcdefg";
    string str2 = "abscdvef";


    cout << "LCS length recursion = "<<lcs_recursion(str1, str2)<<endl;
    cout << "LCS length top down = "<<lcs_top_down_dp(str1, str2)<<endl;
    cout << "LCS length bottom up = "<<lcs_bottom_up(str1, str2)<<endl;

  
}

Output:

LCS length recursion = 6
LCS length top down = 6
LCS length bottom up = 6