Longest Common Subsequence

DSA · Dynamic Programming

Theory

The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both in the same order, not necessarily contiguous. The DP table dp[i][j] holds the LCS length of the first i characters of one string and the first j of the other: if the characters match, dp[i][j] = dp[i-1][j-1] + 1, otherwise the maximum of dropping one character from either string. It runs in O(m × n).

Why we use it

LCS underlies diff tools, version control, DNA comparison and spell checking.

When to use it

Use LCS and related 2-D DP (edit distance) for text comparison, plagiarism detection, file diffs and sequence alignment.

How it works

  1. dp table (m+1) x (n+1) of zeros
  2. For each i, j
  3. a[i-1] == b[j-1]? Yes: dp[i][j] = dp[i-1][j-1] + 1. No: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  4. Return dp[m][n]

Syntax

dp[i][j] = dp[i-1][j-1] + 1           if a[i-1] == b[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) otherwise

Time: O(m·n)   Space: O(m·n)

Example

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])
    out, i, j = [], m, n
    while i and j:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))

print(lcs("ABCBDAB", "BDCABA"))
print(lcs("dynamic", "programming"))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic