Find longest common subsequence (LCS)

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

Hint

The algorithm determines the longest common subsequence between two input strings by recursively comparing their characters. It begins by examining the initial characters of both strings. If these characters are identical, a counter is increased, and the algorithm proceeds to compare the remaining portions of both strings. If the characters do not match, the algorithm explores two possibilities: it recursively compares the first string (excluding its first character) with the entire second string, and it recursively compares the entire first string with the second string (excluding its first character). Finally, the algorithm returns the maximum length obtained from these recursive explorations.

• Python
• Javascript
•  Run

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

  mx = float('-inf')

  if s1[0] == s2[0]:
    mx = 1 + count(s1[1:], s2[1:])

  return max(mx, count(s1[1:], s2), count(s1, s2[1:]))

s1 = "abc"
s2 = "acd"

print(count(s1, s2))

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

  let max = -Infinity;

  if (s1[0] === s2[0]) {
    max = 1 + count(s1.slice(1), s2.slice(1));
  }

  return Math.max(max, count(s1.slice(1), s2), count(s1, s2.slice(1)));
}

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

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