Longest Common Subsequence: A Dynamic Programming Solution

The "Longest Common Subsequence" (LCS) problem is a well-known challenge in computer science. It involves finding the longest sequence of characters that appear in the same order in both of two given strings.

Problem Statement

Given two strings text1 and text2, find the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order in both strings but isn't necessarily contiguous.

Examples

• Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.

• Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3.

Dynamic Programming Solution

Breaking Down the Solution

• Initialization: Create a 2D array dp with dimensions (len(text1) + 1) x (len(text2) + 1) and initialize all elements to 0.
• Dynamic Programming Iteration: Iterate over each character in text1 and text2. Update dp[i][j] with the length of the LCS up to that point.
• Character Match: If characters match (text1[i - 1] === text2[j - 1]), increment the length of the LCS by 1 from the previous characters' LCS length.
• Character Mismatch: If characters don't match, carry forward the maximum LCS length found so far.
• Return the LCS Length: The value in dp[m][n] gives the length of the LCS.

Conclusion

The LCS problem is a fundamental dynamic programming challenge, demonstrating how to break down a complex problem into smaller sub-problems. It's widely used in text comparison, DNA sequencing, and understanding the principles of building up solutions incrementally.

Rust Solution

Rust strings can't be indexed by position, so text1.chars().collect() materialises each argument into a Vec<char> up front to get the O(1) t1[i - 1] access the inner loop relies on. The grid is built with the nested vec![vec![0usize; n + 1]; m + 1] macro, and the mismatch case calls the integer .max() method — dp[i - 1][j].max(dp[i][j - 1]) — rather than a free Math.max. The inclusive 1..=m range walks the same 1-based indices as the JS version, and the function returns a bare usize via the trailing expression dp[m][n], no return keyword.

Go Solution

Go has no literal for a dynamically-sized 2D slice, so the grid is allocated in two steps: make([][]int, m+1) for the outer slice, then for i := range dp fills each row with make([]int, n+1). Indexing a string with text1[i-1] yields a byte, so the comparison operates directly on bytes rather than decoding runes — unlike the Rust version's Vec<char>. The mismatch branch spells the maximum out with an explicit if dp[i-1][j] > dp[i][j-1] / else instead of a helper, and m, n := len(text1), len(text2) grabs both lengths in a single := assignment.