Longest Common Subsequence
Define the LCS recurrence for two strings, fill the 2D table, and reconstruct the actual subsequence by back-tracing through the table.
Longest Common Subsequence is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What is a Subsequence?
A subsequence of a string is formed by deleting some (or no) characters without changing the order of the remaining characters. For example, 'ACE' is a subsequence of 'ABCDE' but 'AEC' is not (order violated). The Longest Common Subsequence (LCS) of two strings is the longest subsequence that appears in both. 'ABCBDAB' and 'BDCABA' share LCS 'BCBA' or 'BDAB' of length 4.
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # TrueLCS Recurrence Derivation
Define dp[i][j] = length of LCS of text1[:i] and text2[:j]. If the characters match (text1[i-1] == text2[j-1]), we extend the LCS by 1: dp[i][j] = dp[i-1][j-1] + 1. If they don't match, we take the better of skipping a character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base case: dp[0][j] = dp[i][0] = 0 (LCS with empty string is 0).
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2Tracing the LCS Table
For text1='ABCD' and text2='ACBD': Start with all zeros. When characters match (A-A, C-C, B-B if in right position, D-D), dp[i][j] = dp[i-1][j-1] + 1. Otherwise take the max of left/top neighbours. Reading through the filled table shows how the diagonal steps correspond to matching characters. The final value dp[4][4] gives the LCS length.
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')Reconstructing the Actual LCS
To recover the actual LCS string, backtrack through the DP table from dp[m][n]. If text1[i-1] == text2[j-1], this character is in the LCS — record it and move diagonally to (i-1, j-1). If dp[i-1][j] > dp[i][j-1], move up; otherwise move left. Reverse the collected characters at the end since you backtracked. This reconstruction runs in O(m+n) time.
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDABSpace Optimisation to O(n)
The LCS table only needs the current row and the previous row. You can use a 1D array of size n+1 and a variable diagonal to store the value that was at dp[i-1][j-1] before it was overwritten. Iterate left to right for each row. After each cell, the updated dp[j] holds the current row's value, and you save the previous value in diagonal before overwriting.
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4LCS and Edit Distance Relationship
LCS is closely related to Edit Distance (Levenshtein distance). If you know the LCS, you can compute the minimum edit distance using only insertions and deletions: edit_dist = m + n - 2 * LCS(s1, s2). Each character not in the LCS from s1 needs a deletion and each not in the LCS from s2 needs an insertion. Substitution is not counted here since we only allow insert/delete, but this formula is useful for related problems.
def lcs_length(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]
def min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 5Delete Operation for Two Strings
Delete Operation for Two Strings (LeetCode 583) asks the minimum number of deletions to make two strings equal. Characters you keep must be a common subsequence, so you want to maximise the LCS and delete everything else. Answer: m + n - 2 * LCS(s1, s2). This is equivalent to the insert/delete edit distance above. Framing problems in terms of LCS is a powerful reduction technique.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4Longest Common Substring
Do not confuse LCS (subsequence) with Longest Common Substring. A substring is contiguous, so if characters don't match, the count resets to 0 instead of taking the max of neighbours. The recurrence changes to: if characters match dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = 0. Track the maximum value seen across all cells.
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
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
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)LCS for Sequence Comparison
LCS is widely used in diff tools (like Unix diff) to compare files. The edit script between two files is derived from the LCS: lines in the LCS are unchanged, extra lines from file 1 are deleted, and extra lines from file 2 are inserted. Understanding LCS helps you appreciate how version control systems track changes and why merging conflicts occur.
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)Shortest Common Supersequence
The Shortest Common Supersequence (LeetCode 1092) asks for the shortest string that has both s1 and s2 as subsequences. Any LCS character appears once in the supersequence; non-LCS characters from both strings must be included. Length = m + n - LCS(s1, s2). To reconstruct: use the same LCS backtracking but include characters from both strings at non-matching positions.
def shortest_common_supersequence(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])
# Reconstruct
result, i, j = [], m, n
while i>0 and j>0:
if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5LCS Complexity and Interview Tips
The classic LCS algorithm runs in O(m×n) time and O(m×n) space, reducible to O(min(m,n)) with the rolling array trick. Key interview tips: (1) Clearly define what the DP state represents before coding. (2) Handle the match and no-match cases distinctly. (3) When asked to reconstruct the sequence, describe backtracking before coding it. (4) Mention the Longest Increasing Subsequence (LIS) as a related 1D problem solvable in O(n log n) with patience sorting.
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: LCS uses dp[i][j] = dp[i-1][j-1]+1 on match, otherwise max(dp[i-1][j], dp[i][j-1]), the actual sequence is reconstructed by backtracking diagonally on matches and toward the larger neighbour on mismatches, and LCS underlies edit distance, delete operations, shortest common supersequence, and diff tools. Next up we derive the Edit Distance (Levenshtein) recurrence, which adds substitutions to the LCS framework.
Frequently asked questions
Is the “Longest Common Subsequence” lesson free?
Yes — the full text of “Longest Common Subsequence” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Longest Common Subsequence”?
Define the LCS recurrence for two strings, fill the 2D table, and reconstruct the actual subsequence by back-tracing through the table. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Longest Common Subsequence” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Unique Paths and Minimum Path Sum on Grids
- Longest Common Subsequence
- Edit Distance (Levenshtein)
- Space Optimisation for 2D DP