Given two strings, s1 and s2, find length of the longest common subsequence. Return 0 for nothing common.

Hint

This algorithm aims to find the longest common subsequence between two given strings. It works by iterating through each character in both strings. At each step, it checks if the current characters in both strings match. If a match is found, the algorithm increments a counter and continues iterating through the remaining characters in both strings. Keeps track of the maximum length found so far.

# Python implementation

def count(s1, s2):
  if len(s1) <= 0 or len(s2) <= 0:
    return 0

  mx = float('-inf')

  for i in range(len(s1)):
    for j in range(len(s2)):
      if s1[i] == s2[j]:
        mx = max(mx, 1 + count(s1[i + 1:], s2[j + 1:]))

  return mx

s1 = "abc"
s2 = "acd"

print(count(s1, s2))

// Javascript implementation

function count(s1, s2) {
  if (s1.length <= 0 || s2.length <= 0) {
    return 0;
  }

  let max = -Infinity;

  for (let i = 0; i < s1.length; i++) {
    for (let j = 0;  j < s2.length; j++) {
      if (s1.at(i) === s2.at(j)) {
        max = Math.max(max, 1 + count(s1.slice(i + 1), s2.slice(j + 1)));
      }
    }
  }

  return max;
}

const s1 = "abc";
const s2 = "acd";

console.log(count(s1, s2));

Find longest common subsequence (LCS)

Hint