Strings: Find the longest common subsequence between two strings.

Problem Statement:

You are given 2 strings you need to return the longest common subsequence between two strings.

Example

str1 = ABC
str2 = AC
Output: 2

The LCS of the 2 strings is "AC" hence 2.

Solution

The solution is similar to LCS, but here we have 2 different strings.
So here we have to use bottom-up DP, that will track LCS.

if a[i] == b[j], LCS for i and j would be 1.
else we take the largest LCS max(m[i – 1][j], m[i][j – 1]).

Time complexity: O(nm)

The filled DP array will look like:

1 1 1
1 1 1
1 2 2
1 2 2
1 2 2
1 2 3

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

int longest_common_subsequence(string &a, string &b)
{
  vector<vector<short>> m(a.size() + 1, vector<short>(b.size() + 1));

  for (auto i = 1; i <= a.size(); ++i)
  {
    for (auto j = 1; j <= b.size(); ++j)
    {
      if (a[i - 1] == b[j - 1]) 
         m[i][j] = m[i - 1][j - 1] + 1;
      else 
         m[i][j] = max(m[i - 1][j], m[i][j - 1]);
    }
  }

  return m[a.size()][b.size()];
}

int main() 
{ 
   string a = "abccde"; 
   string b = "ace"; 

   cout<<"The LCS of 2 strings is = "<<longest_common_subsequence(a, b)<<endl;

   return 0; 
} 

Output:

The LCS of 2 strings is = 3