Visualizers

LCS Visualizer

Compute the Longest Common Subsequence using a 2D DP matrix.

native Client-side

String A (max 8 chars)

String B (max 8 chars)

Speed

Ready to compute.

Execution Log

LCS Length: -

LCS Sequence: -

Current Action:

Idle

Legend:

Uncomputed

Active Lookups

Match (Diagonal step)

Backtrack Path

Longest Common Subsequence (LCS)

The Longest Common Subsequence is a classic computer science problem. Given two sequences, find the length of the longest subsequence present in both. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguously.

Dynamic Programming Relation

For two strings $S_1$ and $S_2$:

If $S_1[i] == S_2[j]$: $DP[i][j] = DP[i-1][j-1] + 1$ (matching diagonal transition)
If $S_1[i] \neq S_2[j]$: $DP[i][j] = max(DP[i-1][j], DP[i][j-1])$ (lookup left and top values)

Implementation

function lcs(s1, s2) {
  const m = s1.length;
  const n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[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(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[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]

public class LCS {
    public static int lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.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];
    }
}

#include <string>
#include <vector>
#include <algorithm>

int lcs(const std::string& s1, const std::string& s2) {
    int m = s1.length();
    int n = s2.length();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

Related Tools

Big-O Visualizer

Interactive growth-curve chart for common complexity classes.

Data Structure Visualizer

Animated operations on linked lists, trees, stacks and hash tables.

Algorithm Visualizer

Step-through animations for sorting and pathfinding algorithms.