Suppose you are given two strings. You need to find the length of the longest common subsequence between these two strings.

longest-common-subsequence.js

function longestCommonSubsequence(str1, str2) {
  // prepare array m*n for top down memoization
  const dp = Array(str1.length).fill().map(() => Array(str2.length).fill(null))
  return rec(0, 0, str1, str2, dp)
}

function rec(i1, i2, str1, str2, dp) {
  if (i1 >= str1.length || i2 >= str2.length) {
    return 0
  }

  if (dp[i1][i2] != null) {
    return dp[i1][i2]
  }

  // if characters match, we increment both pointers and our value increases by one
  if (str1[i1] === str2[i2]) {
    dp[i1][i2] = rec(i1 + 1, i2 + 1, str1, str2, dp) + 1;
  } else {
    // if characters dont match, we need to increment them separately to start separate recursion subtrees,
    // to see which one will give us better result
    dp[i1][i2] = Math.max(rec(i1 + 1, i2, str1, str2, dp), rec(i1, i2 + 1, str1, str2, dp))
  }

  return dp[i1][i2]
}


export {longestCommonSubsequence};

// tc: (without top down memoization)
// depth of the recursion tree is m + n where m and n are lengths of input strings
// why? well if we dont encounter matches,
// we move the pointer of the first string, while keeping the pointer of the second string at 0
// and when we reach the end of the first string, we start moving the pointer of the second string,
// while keeping the pointer of the first string at the end, thus deepening the call stack by first by m, then by n
// imagine m=3 and n=4
// (0, 0)
// (1, 0)
// (2, 0)
// (3, 0) -> causes 2 rec calls, (4, 0) (base case), and (3, 1)
// (3, 1) will cause the (3, 2) (3, 3) and etc calls
// so complexity will be O(2^m+n)
// by adding memoization, we only need to solve O(m*n) subproblems
// so we reduce tc to O(m*n)
// sc: O(m*n)

function longestCommonSubsequenceBottomUp(str1, str2) {
  // dp is a 2-dimensional array,
  // where dp[i][j] is a solution to the following subproblem:
  // what is the length of the longest common subsequence when i points to (i-1) character in str1, j points to (j-1) character in str2

  // dp[i][j] is determined by the following
  // if characters str1[i-1] str2[j-1] are equal
  // we add 1 to the solution of the previous subproblem dp[i-1][j-1] (moving both pointers back one step)
  // if they are not equal
  // we get maximum of the two previous subproblems dp[i][j-1] dp[i-1][j] (moving each pointer back separately)

  // index 0 in dp represents an empty string

  const dp = Array(str1.length + 1).fill().map(() => Array(str2.length + 1).fill(0));
  for (let i = 1; i <= str1.length; ++i) {
    for (let j = 1; j <= str2.length; ++j) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1]
      } else {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
      }
    }
  }
  return dp[str1.length][str2.length]
}

export {longestCommonSubsequenceBottomUp};

// bottom up tc: O(m*n) sc: O(m*n)