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

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Find longest common subsequence (LCS), but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

# Python implementation

cache = None

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

  global cache
  if not cache:
    cache = [[None for _ in range(len(s2))] for _ in range(len(s1))]

  if not cache[len(s1) - 1][len(s2) - 1]:
    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:]))

    cache[len(s1) - 1][len(s2) - 1] = mx

  return cache[len(s1) - 1][len(s2) - 1]

s1 = "abc"
s2 = "acd"

print(count(s1, s2))

// Javascript implementation

let cache = null;

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

  if (cache === null) {
    cache = []

    for (let i = 0; i < s1.length; i++) {
      cache[i] = [];
    }
  }

  if (cache[s1.length - 1][s2.length - 1] === undefined) {
    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)));
        }
      }
    }

    cache[s1.length - 1][s2.length - 1] = max;
  }

  return cache[s1.length - 1][s2.length - 1];
}

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

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

Find longest common subsequence (LCS) (Memoization)

Hint