Introduction to Longest Common Subsequence
The Longest Common Subsequence (LCS) problem is one of the most fundamental problems in computer science and dynamic programming. Given two strings (or sequences), the goal is to find the longest subsequence that appears in both strings in the same order, though not necessarily consecutively.
For example, given the strings "ABCBDAB" and "BDCAB", the longest common subsequence is "BCAB" with a length of 4. Note that a subsequence differs from a substring — a subsequence does not require elements to be contiguous, only ordered.
Subsequence vs Substring
Understanding the difference between a subsequence and a substring is crucial before diving into the algorithm:
- Substring: A contiguous sequence of characters within a string. For
"ABCDEF","CDE"is a substring. - Subsequence: A sequence that can be derived by deleting some characters without changing the order of the remaining elements. For
"ABCDEF","ACE"is a subsequence but not a substring.
Why LCS Matters
The LCS problem has wide-ranging applications across multiple domains in software development. Understanding how to solve it efficiently is valuable for any developer working with text processing, version control, or bioinformatics.
Real-World Applications
- Version Control Systems: Tools like Git use LCS algorithms to compute diffs between file versions, showing what lines were added, deleted, or modified.
- Bioinformatics: DNA and protein sequence alignment relies heavily on LCS to find evolutionary relationships between organisms.
- Plagiarism Detection: Comparing documents to find similar passages often involves LCS-based algorithms.
- Spell Checkers and Auto-Correction: Suggesting corrections by finding the closest matching words.
- Data Compression: Some compression algorithms use LCS to identify repeated patterns.
- File Comparison Tools: Applications like
diffuse LCS to highlight differences between files.
Understanding the Problem Step by Step
Before jumping into code, let us build intuition about how to solve this problem. Consider two strings: S1 = "ABCD" and S2 = "ACBD".
A naive approach would be to generate all possible subsequences of one string and check if each exists in the other. However, a string of length n has 2^n possible subsequences, making this approach exponential and impractical for large inputs.
Instead, we use dynamic programming. The key insight is that the LCS problem exhibits two important properties:
- Optimal Substructure: The LCS of two strings contains the LCS of their prefixes as subproblems.
- Overlapping Subproblems: The same subproblems are solved repeatedly, making memoization or tabulation beneficial.
The Recurrence Relation
Let LCS(i, j) represent the length of the longest common subsequence of the first i characters of string S1 and the first j characters of string S2. The recurrence relation is:
If S1[i-1] == S2[j-1]:
LCS(i, j) = LCS(i-1, j-1) + 1
Else:
LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))
The base case is LCS(0, j) = 0 and LCS(i, 0) = 0 for all valid i and j, since the LCS with an empty string is always 0.
Implementing LCS in Go
Now let us implement the solution in Go. We will start with a basic dynamic programming approach using a 2D table.
Basic DP Solution: Finding the Length
This implementation computes the length of the longest common subsequence using a bottom-up dynamic programming approach:
package main
import "fmt"
func LCSLength(s1, s2 string) int {
m := len(s1)
n := len(s2)
// Create a 2D DP table of size (m+1) x (n+1)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// Build the table in bottom-up fashion
for i := 1; i <= m; i++ {
for 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] = max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[m][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
s1 := "ABCBDAB"
s2 := "BDCAB"
result := LCSLength(s1, s2)
fmt.Printf("Length of LCS of \"%s\" and \"%s\" is: %d\n", s1, s2, result)
}
When you run this program, the output will be:
Length of LCS of "ABCBDAB" and "BDCAB" is: 4
Reconstructing the Actual Subsequence
Knowing the length is useful, but often we need the actual subsequence itself. We can reconstruct it by backtracking through the DP table:
package main
import "fmt"
func LCSString(s1, s2 string) string {
m := len(s1)
n := len(s2)
// Create a 2D DP table
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// Fill the DP table
for i := 1; i <= m; i++ {
for 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] = max(dp[i-1][j], dp[i][j-1])
}
}
}
// Backtrack to find the LCS string
lcs := make([]byte, dp[m][n])
index := dp[m][n] - 1
i, j := m, n
for i > 0 && j > 0 {
if s1[i-1] == s2[j-1] {
lcs[index] = s1[i-1]
index--
i--
j--
} else if dp[i-1][j] > dp[i][j-1] {
i--
} else {
j--
}
}
return string(lcs)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
s1 := "ABCBDAB"
s2 := "BDCAB"
result := LCSString(s1, s2)
fmt.Printf("LCS of \"%s\" and \"%s\" is: \"%s\"\n", s1, s2, result)
}
The output will be:
LCS of "ABCBDAB" and "BDCAB" is: "BCAB"
Optimizing Space Complexity
The basic solution uses O(m * n) space for the DP table. However, we can optimize this to O(min(m, n)) space when we only need the length of the LCS, since each cell only depends on the current and previous rows.
Space-Optimized Solution
package main
import "fmt"
func LCSLengthOptimized(s1, s2 string) int {
// Ensure s2 is the shorter string to minimize space
if len(s1) < len(s2) {
s1, s2 = s2, s1
}
m := len(s1)
n := len(s2)
// Use two rows instead of a full 2D table
prev := make([]int, n+1)
curr := make([]int, n+1)
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if s1[i-1] == s2[j-1] {
curr[j] = prev[j-1] + 1
} else {
curr[j] = max(prev[j], curr[j-1])
}
}
// Swap rows
prev, curr = curr, prev
// Reset curr for next iteration
for j := range curr {
curr[j] = 0
}
}
return prev[n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
s1 := "AGGTAB"
s2 := "GXTXAYB"
result := LCSLengthOptimized(s1, s2)
fmt.Printf("Length of LCS: %d\n", result)
}
Recursive Approach with Memoization
While the bottom-up approach is generally preferred for LCS, some developers find the top-down recursive approach with memoization more intuitive. Here is how to implement it in Go:
package main
import "fmt"
func LCSMemoized(s1, s2 string) int {
m := len(s1)
n := len(s2)
// Initialize memoization table with -1
memo := make([][]int, m+1)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
return lcsHelper(s1, s2, m, n, memo)
}
func lcsHelper(s1, s2 string, m, n int, memo [][]int) int {
// Base case
if m == 0 || n == 0 {
return 0
}
// Check if already computed
if memo[m][n] != -1 {
return memo[m][n]
}
// If characters match
if s1[m-1] == s2[n-1] {
memo[m][n] = 1 + lcsHelper(s1, s2, m-1, n-1, memo)
return memo[m][n]
}
// If characters don't match, take the maximum
memo[m][n] = max(
lcsHelper(s1, s2, m-1, n, memo),
lcsHelper(s1, s2, m, n-1, memo),
)
return memo[m][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
s1 := "PROGRAMMING"
s2 := "ALGORITHM"
result := LCSMemoized(s1, s2)
fmt.Printf("Length of LCS of \"%s\" and \"%s\" is: %d\n", s1, s2, result)
}
Practical Example: File Diff Utility
Let us build a practical example that demonstrates how LCS can be used to create a simple file diff utility. This example compares two slices of strings (representing lines of text) and shows which lines are common, added, or removed.
package main
import "fmt"
type DiffType int
const (
DiffCommon DiffType = iota
DiffAdded
DiffRemoved
)
type DiffEntry struct {
Type DiffType
Content string
}
func ComputeDiff(oldLines, newLines []string) []DiffEntry {
m := len(oldLines)
n := len(newLines)
// Build DP table
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if oldLines[i-1] == newLines[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 build the diff
var diff []DiffEntry
i, j := m, n
for i > 0 || j > 0 {
if i > 0 && j > 0 && oldLines[i-1] == newLines[j-1] {
diff = append([]DiffEntry{{DiffCommon, oldLines[i-1]}}, diff...)
i--
j--
} else if j > 0 && (i == 0 || dp[i][j-1] >= dp[i-1][j]) {
diff = append([]DiffEntry{{DiffAdded, newLines[j-1]}}, diff...)
j--
} else if i > 0 {
diff = append([]DiffEntry{{DiffRemoved, oldLines[i-1]}}, diff...)
i--
}
}
return diff
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
oldFile := []string{
"package main",
"import \"fmt\"",
"func main() {",
" fmt.Println(\"Hello\")",
"}",
}
newFile := []string{
"package main",
"import \"fmt\"",
"func main() {",
" fmt.Println(\"Hello, World!\")",
" fmt.Println(\"Goodbye\")",
"}",
}
diff := ComputeDiff(oldFile, newFile)
fmt.Println("=== File Diff ===")
for _, entry := range diff {
switch entry.Type {
case DiffCommon:
fmt.Printf(" %s\n", entry.Content)
case DiffAdded:
fmt.Printf("+ %s\n", entry.Content)
case DiffRemoved:
fmt.Printf("- %s\n", entry.Content)
}
}
}
The output of this diff utility will be:
=== File Diff ===
package main
import "fmt"
func main() {
- fmt.Println("Hello")
+ fmt.Println("Hello, World!")
+ fmt.Println("Goodbye")
}
Best Practices
When implementing and using LCS algorithms in production code, consider the following best practices:
Choose the Right Approach
- Use the bottom-up DP approach for most cases. It avoids recursion overhead and is generally faster in practice.
- Use the memoized recursive approach when only a small portion of the DP table is actually needed, as it computes only the required subproblems.
- Use the space-optimized approach when memory is constrained and you only need the LCS length.
Handle Edge Cases
Always validate your inputs before processing. Empty strings, nil values, and very long strings should all be handled gracefully:
func LCSSafe(s1, s2 string) (int, error) {
if len(s1) == 0 || len(s2) == 0 {
return 0, nil
}
// Guard against extremely large inputs
const maxInputSize = 10000
if len(s1) > maxInputSize || len(s2) > maxInputSize {
return 0, fmt.Errorf("input too large: max allowed length is %d", maxInputSize)
}
// Proceed with normal LCS computation
return LCSLength(s1, s2), nil
}
Use Rune Slices for Unicode Support
Go strings are UTF-8 encoded, and indexing by byte can cause issues with multi-byte characters. For Unicode strings, convert to rune slices first:
func LCSUnicode(s1, s2 string) int {
r1 := []rune(s1)
r2 := []rune(s2)
m := len(r1)
n := len(r2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if r1[i-1] == r2[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]
}
Consider Variations for Specific Use Cases
- Longest Common Substring: If you need contiguous matches, modify the recurrence to reset to 0 when characters do not match instead of carrying forward the maximum.
- Shortest Common Supersequence: This is related to LCS and can be derived from the LCS length:
SCS_length = len(s1) + len(s2) - LCS_length. - Edit Distance: The Levenshtein distance algorithm is a generalization of LCS that also accounts for substitutions.
Benchmark and Profile
For performance-critical applications, always benchmark your implementation. Go's built-in benchmarking tools make this straightforward:
package main
import "testing"
func BenchmarkLCSLength(b *testing.B) {
s1 := "ABCBDABABCBDABABCBDABABCBDAB"
s2 := "BDCABBDCABBDCABBDCABBDCAB"
for i := 0; i < b.N; i++ {
LCSLength(s1, s2)
}
}
func BenchmarkLCSLengthOptimized(b *testing.B) {
s1 := "ABCBDABABCBDABABCBDABABCBDAB"
s2 := "BDCABBDCABBDCABBDCABBDCAB"
for i := 0; i < b.N; i++ {
LCSLengthOptimized(s1, s2)
}
}
Run benchmarks with go test -bench=. to compare performance between implementations and identify bottlenecks.
Complexity Analysis
Understanding the time and space complexity of each approach helps you make informed decisions:
- Bottom-up DP: Time complexity is
O(m * n), space complexity isO(m * n)for the full table orO(min(m, n))for the space-optimized version. - Memoized Recursion: Time complexity is
O(m * n), space complexity isO(m * n)for the memo table plusO(m + n)for the recursion stack. - Naive Recursive (without memoization): Time complexity is
O(2^(m+n)), which is exponential and should never be used in practice.
Conclusion
The Longest Common Subsequence problem is a cornerstone of dynamic programming that every developer should understand. In this tutorial, we explored what LCS is, why it matters in real-world applications like version control and bioinformatics, and how to implement it in Go using multiple approaches. We covered the standard bottom-up DP solution, a space-optimized variant, a memoized recursive approach, and a practical file diff utility that demonstrates the algorithm in action. By following the best practices outlined — including handling edge cases, supporting Unicode, choosing the right approach for your constraints, and benchmarking your code — you will be well-equipped to apply LCS in your own projects. Whether you are building a diff tool, analyzing sequences, or solving interview problems, the techniques covered here provide a solid foundation for working with one of computer science's most essential algorithms.