Longest Common Subsequence

LCS length, reconstruction, and edit distance variant.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

LCS Length

Given two strings, find length of longest common subsequence (not necessarily contiguous). Classic 2D DP: dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1].

Golcs-length.go

19 linesLn 1, Col 1Go

If chars match: extend LCS (dp[i-1][j-1] + 1). If not: max of skipping char from text1 (dp[i-1][j]) or text2 (dp[i][j-1]).

Reconstructing LCS

Goreconstruct-lcs-string.go

36 linesLn 1, Col 1Go

Walk backwards from dp[m][n]. If chars match, include in result. Otherwise go to larger neighbor (prefer up if equal).

Edit Distance

Minimum operations (insert, delete, replace) to convert word1 to word2. Very similar to LCS: dp[i][j] = edit distance of word1[0..i-1] to word2[0..j-1].

Goedit-distance-(levenshtein).go

24 linesLn 1, Col 1Go

Base cases: convert to/from empty string. If chars match, no operation needed. Else: 1 + min of three operations.

Variants

Shortest Common Supersequence: len(s1) + len(s2) - LCS(s1,s2)
Delete to make equal: len(s1) + len(s2) - 2*LCS(s1,s2)
Distinct subsequences: Count how many times s2 appears as subsequence in s1
Longest Palindromic Subsequence: LCS(s, reverse(s))

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.