SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Advanced

Longest Common Subsequence Visualizer

dp[i][j] is the LCS of the first i letters of A and the first j letters of B. A match adds 1 to the diagonal. Otherwise take the bigger of up and left.

Start the Longest Common Subsequence simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(m·n)
Average timeO(m·n)
Worst timeO(m·n)
Extra spaceO(m·n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. The empty row and column are 0: an empty string shares no letters.
  2. A ≠ B. Take max(up 0, left 0) = 0.
  3. A ≠ D. Take max(up 0, left 0) = 0.
  4. A ≠ C. Take max(up 0, left 0) = 0.
  5. A = A. A match: diagonal 0 + 1 = 1.
  6. A ≠ B. Take max(up 0, left 1) = 1.
  7. A = A. A match: diagonal 0 + 1 = 1.
  8. B = B. A match: diagonal 0 + 1 = 1.
  9. B ≠ D. Take max(up 0, left 1) = 1.
  10. B ≠ C. Take max(up 0, left 1) = 1.
  11. B ≠ A. Take max(up 1, left 1) = 1.
  12. B = B. A match: diagonal 1 + 1 = 2.
  13. B ≠ A. Take max(up 1, left 2) = 2.
  14. C ≠ B. Take max(up 1, left 0) = 1.
  15. C ≠ D. Take max(up 1, left 1) = 1.
  16. C = C. A match: diagonal 1 + 1 = 2.
  17. C ≠ A. Take max(up 1, left 2) = 2.
  18. C ≠ B. Take max(up 2, left 2) = 2.
  19. C ≠ A. Take max(up 2, left 2) = 2.
  20. B = B. A match: diagonal 0 + 1 = 1.
  21. … 20 more steps …
  22. B ≠ A. Take max(up 3, left 2) = 3.
  23. B = B. A match: diagonal 3 + 1 = 4.
  24. B ≠ A. Take max(up 4, left 4) = 4.
  25. The LCS length is 4. Tracing back gives "BCBA".

Try it with your own input →

2D DP: longest common subsequence in Java, Python, C++, C and JavaScript

int lcs(String a, String b) {
  int[][] dp = new int[m + 1][n + 1];
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (a.charAt(i - 1) == b.charAt(j - 1))
        dp[i][j] = dp[i - 1][j - 1] + 1;
      else
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
}
def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
int lcs(const string& a, const string& b) {
  int m = a.size(), n = b.size();
  vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (a[i - 1] == b[j - 1])
        dp[i][j] = dp[i - 1][j - 1] + 1;
      else
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
}
#include <string.h>

int lcs(const char* a, const char* b) {
  int m = strlen(a), n = strlen(b);
  int dp[m + 1][n + 1];
  memset(dp, 0, sizeof dp);
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (a[i - 1] == b[j - 1])
        dp[i][j] = dp[i - 1][j - 1] + 1;
      else
        dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
    }
  }
  return dp[m][n];
}
function lcs(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1])
        dp[i][j] = dp[i - 1][j - 1] + 1;
      else
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
}

In an interview

LeetCode 1143, Longest Common Subsequence. The same table solves 72 Edit Distance and 583 Delete Operation for Two Strings.

Almost every two-string DP uses this (m + 1) × (n + 1) table with an empty first row and column. Draw it before coding.

More dynamic programming