Longest Common Subsequence

stringsubsequencediff

Press play to start

1function lcs(s1: string, s2: string): number {
const m = s1.length, 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]
13}

Step 1/0

Custom array:

Complexity

Best:O(m·n)
Average:O(m·n)
Worst:O(m·n)
Space:O(m·n)

Description

Finds the longest subsequence present in both strings in the same relative order (not necessarily contiguous).

When to use

Diff tools (git), spell checkers, bioinformatics (DNA comparison), version control systems.