Table of Contents

Problem

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Source

Analysis

An intuitive way to do this is to track a pointer on each string, counting only if the other pointer matches. If they match, the answer is 1 plus the LCS of the rest of both string. That’s an easy recursive call.

If they don’t match, the LCS is either in string A or string B. I’ll demonstrate

Let’s say we have strings abced and acfe. The LCS is ace.

+
a b c   e d
a   c b e
+

The a matches, so we move both cursors knowing that our LCS is at least that a, plus the LCS between bced and cbe.

  p1
  +
a b c   e d
a   c b e
    +
    p2

Now b and c are nonmatching, so the LCS could start with either one of those. We can reduce the problem space by removing a char (incrementing a p) from one of the strings and recursing on that.

However, we must check both possibilities. We must check calculate the LCS between bced/be and ced/cbe, and use the greatest of the two answers.

Solution

Naiive Solution

Here’s my first solution, with no memoization.

function longestCommonSubsequence(text1: string, text2: string): number {
  return longestCommonSubsequenceRecurse(text1, text2, 0, 0)
};


function longestCommonSubsequenceRecurse(text1: string, text2: string, p1: number, p2: number): number {
  if (p1 < text1.length && p2 < text2.length) {
    const c1 = text1[p1]
    const c2 = text2[p2]
    if (c1 === c2) {
      const len = 1 + longestCommonSubsequenceRecurse(text1, text2, p1+1, p2+1)
      return len
    }
    else {
      // Find each LCS with a letter chopped off either word
      const len1 = longestCommonSubsequenceRecurse(text1, text2, p1+1, p2)
      const len2 = longestCommonSubsequenceRecurse(text1, text2, p1, p2+1)
      const longest = Math.max(len1, len2)

      return longest
    }
  }

  return 0
};

Implementation

Here’s an optimized version. For each run, we memoize the solutions by cursor position. Hashing numbers is much easier than hashing text objects.

const memod: Map<string, number> = new Map<string, number>();

function getHash(p1: number, p2: number): string {
    return `${p1}:${p2}`;
}

function setMemo(p1: number, p2: number, length: number) {
    memod.set(getHash(p1, p2), length);
}

function longestCommonSubsequence(text1: string, text2: string): number {
    memod.clear()
    return longestCommonSubsequenceRecurse(text1, text2, 0, 0);
}

function longestCommonSubsequenceRecurse(text1: string, text2: string, p1: number, p2: number): number {
    const hash = getHash(p1, p2);
    if (memod.has(hash)) {
        return memod.get(hash);
    }

    if (p1 >= text1.length || p2 >= text2.length) {
        return 0;
    }

    if (text1[p1] === text2[p2]) {
        const len = 1 + longestCommonSubsequenceRecurse(text1, text2, p1 + 1, p2 + 1);
        setMemo(p1, p2, len);
        return len;
    } else {
        const len1 = longestCommonSubsequenceRecurse(text1, text2, p1 + 1, p2);
        const len2 = longestCommonSubsequenceRecurse(text1, text2, p1, p2 + 1);
        const longest = Math.max(len1, len2);
        setMemo(p1, p2, longest);
        return longest;
    }
}

Solution

Algorithm Lecture

Leetcode: Longest Common Subsequence

Problem

Analysis

Solution

Naiive Solution

Implementation

Solution