Ah yes, the classic. You have ABCDGH and AEDFHR and ADH is common between the two. So 3 should be the output.

Yes we can brute force, but math says there will be O(2^m * 2^n) (where m and n are lengths of the two strings ofc) combinations which doesn’t look good.

We can be recursive about it!

If s1[i] == s2[j]: 
    LCS(i,j) = 1 + LCS(i+1, j+1)
Else: 
    LCS(i,j) = max(LCS(i+1, j), LCS(i, j+1))

So if we compare ABC and AC, A and A matches, so LCS now is equal to 1 + LCS("BC", "C")

For "BC" vs "C": 'B' ≠ 'C', so we now try:

LCS("C", "C") = 1 (characters match)

LCS("BC", "") = 0 (one string is empty)

Take maximum = 1

Thus, total LCS length = 1 + 1 = 2

But this is O(2^(m+n)). Better, but here’s where we can be dynamic!

What if we have a matrix. And then we take the first letter from the word spanning the column and match it with all the letters of the word spanning the row.

     A E D F H R
   0 0 0 0 0 0 0
A  0 1 1 1 1 1 1
B  0 1 1 1 1 1 1  
C  0 1 1 1 1 1 1
D  0 1 1 2 2 2 2
G  0 1 1 2 2 2 2
H  0 1 1 2 2 3 3

A matches A, make it +1, and copy the increased value to rest of the row. Copy this entire row to the next row as initial values and match again!

Now if we match again, do a +1 in that position and copy that value to the rest of the row again, else if no match, keep it as is. Continue this till the end. And the value at the bottom right corner becomes our answer! We preserved order and didn’t match multiple letters with one. All under O(n * m)!

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
   string s1 = "ABCDGH";
   string s2 = "AEDFHR";

   int m = s1.length();
   int n = s2.length();

   vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

   for (int i = 1; i <= m; i++) {
       for (int j = 0; j <= n; j++) 
           dp[i][j] = dp[i-1][j];

       for (int j = 1; j <= n; j++) {
           if (s1[i-1] == s2[j-1]) {
               dp[i][j] = 1 + dp[i-1][j-1];

               for (int k = j+1; k <= n; k++) 
                   dp[i][k] = max(dp[i][k], dp[i][j]);
           }
       }
   }

   cout << "String 1: " << s1 << endl;
   cout << "String 2: " << s2 << endl;
   cout << "LCS Length: " << dp[m][n] << endl;

   return 0;
}

If this is the wrong solution, I’m not responsible for your troubles. Do drop me a follow on Twitter, I don’t rage bait or shitpost (in general), mostly boring CS and occasional football stuff if that interests you.