Longest Common Subsequence in DSA Rust - Execution Trace

Concept Flow - Longest Common Subsequence

Start with two strings

↓

Create DP table with size (m+1)x(n+1)

↓

Fill first row and column with 0

↓

For each character pair (i,j):

↓

If chars match: dp[i

↓

Else: dp[i

↓

DP table filled

↓

Trace back from dp[m

↓

Output LCS length and sequence

↓

End

Build a table comparing prefixes of two strings, fill it using matches or max of neighbors, then trace back to get the longest common subsequence.

Execution Sample

DSA Rust

let s1 = "ABCBDAB";
let s2 = "BDCABA";
// Build dp table
// Fill dp
// Trace back to get LCS

This code finds the longest common subsequence between two strings by building and filling a DP table, then tracing back the sequence.

Execution Table

Step	Operation	DP Table State (partial)	Pointer Changes	Visual State
0	Initialize DP table with zeros	[[0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0]]	None	DP table empty with 8 rows and 7 columns (for s1 length 7 and s2 length 6)
1	Compare s1[0]='A' and s2[0]='B' (no match)	[[0,0,0,0,0,0,0], [0,0,0,0,0,0,0], ...]	dp[1][1] = max(dp[0][1], dp[1][0]) = 0	No increment, dp[1][1] stays 0
2	Compare s1[0]='A' and s2[1]='D' (no match)	[[0,0,0,0,0,0,0], [0,0,0,0,0,0,0], ...]	dp[1][2] = max(dp[0][2], dp[1][1]) = 0	No increment, dp[1][2] stays 0
3	Compare s1[0]='A' and s2[2]='C' (no match)	[[0,0,0,0,0,0,0], [0,0,0,0,0,0,0], ...]	dp[1][3] = max(dp[0][3], dp[1][2]) = 0	No increment, dp[1][3] stays 0
4	Compare s1[0]='A' and s2[3]='A' (match)	[[0,0,0,0,0,0,0], [0,0,0,0,1,0,0], ...]	dp[1][4] = dp[0][3] + 1 = 1	Increment dp[1][4] to 1
5	Compare s1[0]='A' and s2[4]='B' (no match)	[[0,0,0,0,0,0,0], [0,0,0,0,1,1,0], ...]	dp[1][5] = max(dp[0][5], dp[1][4]) = 1	Carry forward 1
6	Compare s1[0]='A' and s2[5]='A' (match)	[[0,0,0,0,0,0,0], [0,0,0,0,1,1,1], ...]	dp[1][6] = dp[0][5] + 1 = 1	Increment dp[1][6] to 1
7	Continue filling dp for s1[1]='B'	[[0,0,0,0,0,0,0], [0,0,0,0,1,1,1], [0,1,1,1,1,2,2], ...]	Fill row 2 based on matches and max neighbors	DP table grows with values reflecting LCS lengths
8	Fill dp completely for all characters	[[0,0,0,0,0,0,0], [0,0,0,0,1,1,1], [0,1,1,1,1,2,2], [0,1,1,2,2,2,2], [0,1,2,2,2,3,3], [0,1,2,2,3,3,3], [0,1,2,3,3,3,4], [0,1,2,3,4,4,4]]	None	DP table fully filled with LCS lengths
9	Trace back from dp[7][6]=4 to find LCS	None	Move diagonally if chars match, else move to max neighbor	LCS found is 'BCAB' or 'BDAB'
10	End	None	LCS length = 4, sequence = 'BCAB'	Process complete

💡 DP table fully filled and LCS traced back, no more steps

Variable Tracker

Variable	Start	After Step 4	After Step 8	Final
dp	All zeros 8x7 matrix	Partial fill with dp[1][4]=1	Fully filled DP table with LCS lengths	Final DP table used for traceback
i	Not started	1	7	7 (length of s1)
j	Not started	4	6	6 (length of s2)
LCS length	0	1	4	4
LCS sequence	Empty	Not started	Not started	'BCAB' or 'BDAB'

Key Moments - 3 Insights

Why do we add 1 to dp[i-1][j-1] when characters match?

Because matching characters extend the previous longest subsequence by one, as shown in execution_table step 4 where dp[1][4] = dp[0][3] + 1.

Why do we take the max of dp[i-1][j] and dp[i][j-1] when characters don't match?

Because the longest subsequence so far is the best between ignoring one character from either string, as seen in steps 1-3 where no match leads to max of neighbors.

How do we find the actual LCS sequence after filling the DP table?

By tracing back from dp[m][n], moving diagonally when characters match, or moving to the neighbor with the larger value otherwise, as explained in step 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of dp[1][4]?

A 1

B 0

C 2

D Undefined

💡 Hint

Refer to execution_table row with Step 4 showing dp[1][4] = dp[0][3] + 1 = 1

At which step does the DP table become fully filled?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Check execution_table row with Step 8 describing the fully filled DP table

If s1 and s2 had no matching characters, what would be the final LCS length in the DP table?

A Length of s1

B Length of s2

C 0

D Sum of lengths of s1 and s2

💡 Hint

Look at variable_tracker dp initial state and how no matches keep dp values at 0

Concept Snapshot

Longest Common Subsequence (LCS):
- Use two strings s1 and s2
- Create DP table of size (len(s1)+1) x (len(s2)+1)
- Fill first row and column with 0
- For each i,j: if s1[i-1]==s2[j-1], dp[i][j]=dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1])
- LCS length = dp[len(s1)][len(s2)]
- Trace back from dp end to get LCS sequence

Full Transcript

Longest Common Subsequence finds the longest sequence common to two strings. We start by creating a table with rows for each character of the first string plus one, and columns for the second string plus one. We fill the first row and column with zeros because an empty string has zero common subsequence with any string. Then, for each character pair, if they match, we add one to the value from the diagonal cell above-left. If they don't match, we take the maximum value from the cell above or to the left. After filling the table, the bottom-right cell shows the length of the longest common subsequence. To find the actual sequence, we trace back from this cell, moving diagonally when characters match or moving to the neighbor with the larger value otherwise. This process is shown step-by-step in the execution table and variable tracker.

Practice

1. What does the Longest Common Subsequence (LCS) between two strings represent?

easy

A. The longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively.

B. The longest substring that appears exactly the same in both strings.

C. The shortest sequence of characters that can be removed to make the strings identical.

D. The total number of characters that differ between the two strings.

Solution

1. Step 1: Understand the definition of LCS

   The LCS is the longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively.

2. Step 2: Differentiate from substring and other concepts

   Unlike substring, LCS does not require characters to be consecutive. It is about order and presence.

3. Final Answer:

   The longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively. -> Option A

4. Quick Check:

   LCS = longest ordered common sequence [OK]

Hint: LCS keeps order, skips gaps, unlike substring [OK]

Common Mistakes:

• Confusing LCS with longest common substring
• Thinking characters must be consecutive
• Mixing LCS with edit distance

2. Which of the following Rust function signatures correctly represents a function to compute LCS length between two string slices?

easy

A. fn lcs_length(s1: &str, s2: &str) -> bool

B. fn lcs_length(s1: String, s2: String) -> &str

C. fn lcs_length(s1: &String, s2: &String) -> String

D. fn lcs_length(s1: &str, s2: &str) -> usize

Solution

1. Step 1: Identify correct parameter types for string inputs

   Using &str is idiomatic for string slices in Rust, allowing borrowing without ownership transfer.

2. Step 2: Identify correct return type for LCS length

   LCS length is a number, so usize is appropriate. Returning &str or String is incorrect for length.

3. Final Answer:

   fn lcs_length(s1: &str, s2: &str) -> usize -> Option D

4. Quick Check:

   Input: &str, Output: usize for length [OK]

Hint: Use &str for inputs and usize for length output [OK]

Common Mistakes:

• Returning &str or String instead of length
• Using owned String unnecessarily
• Returning bool instead of length

3. What is the output of the following Rust code snippet that computes the LCS length of "AGGTAB" and "GXTXAYB"?

fn main() {
    let s1 = "AGGTAB";
    let s2 = "GXTXAYB";
    let lcs_len = lcs_length(s1, s2);
    println!("{}", lcs_len);
}

fn lcs_length(s1: &str, s2: &str) -> usize {
    let m = s1.len();
    let n = s2.len();
    let mut dp = vec![vec![0; n + 1]; m + 1];
    for i in 1..=m {
        for j in 1..=n {
            if s1.as_bytes()[i - 1] == s2.as_bytes()[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[m][n]
}

medium

A. 6

B. 3

C. 4

D. 5

Solution

1. Step 1: Understand the input strings and LCS algorithm

   Strings are "AGGTAB" and "GXTXAYB". The code uses dynamic programming to find LCS length.

2. Step 2: Trace the LCS calculation

   The LCS is "GTAB" with length 4. The code correctly computes this.

3. Step 3: Verify carefully

   Common subsequence: G T A B (positions match in order). Length is 4.

4. Final Answer:

   4 -> Option C

5. Quick Check:

   LCS length of "AGGTAB" and "GXTXAYB" = 4 [OK]

Hint: Trace matching chars in order, ignore gaps [OK]

Common Mistakes:

• Counting common characters not in order
• Confusing substring with subsequence
• Off-by-one errors in indexing

4. Identify the bug in the following Rust function that attempts to compute the LCS length:

fn lcs_length(s1: &str, s2: &str) -> usize {
    let m = s1.len();
    let n = s2.len();
    let mut dp = vec![vec![0; n]; m];
    for i in 1..m {
        for j in 1..n {
            if s1.as_bytes()[i] == s2.as_bytes()[j] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[m - 1][n - 1]
}

medium

A. The dp vector is initialized with size m x n instead of (m+1) x (n+1).

B. The loops start from 0 instead of 1, causing index errors.

C. The loops use 1..=m and 1..=n instead of 1..m and 1..n, causing out of bounds.

D. The function returns dp[m][n] which is out of bounds.

Solution

1. Step 1: Check dp vector initialization

   The dp vector is initialized as m x n, but it should be (m+1) x (n+1) to handle base cases and indexing from 1.

2. Step 2: Understand loop ranges and indexing

   Loops start from 1..

3. Final Answer:

   The dp vector is initialized with size m x n instead of (m+1) x (n+1). -> Option A

4. Quick Check:

   dp size must be (m+1) x (n+1) [OK]

Hint: dp table size must include extra row and column [OK]

Common Mistakes:

• Initializing dp with wrong size
• Incorrect loop ranges causing panic
• Wrong indexing of string bytes

5. Given two strings, write a Rust function that returns the actual Longest Common Subsequence string (not just length). Which approach below correctly reconstructs the LCS from the dp table?

hard

A. Start from dp[0][0], move right or down collecting characters whenever dp[i][j] increases.

B. Start from dp[m][n], move diagonally up-left if characters match, else move to the cell with the larger value, collecting matched characters in reverse order.

C. Traverse dp table row-wise and append characters when dp[i][j] is non-zero.

D. Reverse both strings and find LCS length, then reverse the result to get LCS string.

Solution

1. Step 1: Understand dp table usage for reconstruction

   The dp table stores lengths of LCS for substrings. To reconstruct, start from dp[m][n] and move backwards.

2. Step 2: Trace path to build LCS string

   If characters match at s1[i-1] and s2[j-1], move diagonally up-left and add character. Else move to cell with larger dp value (up or left).

3. Step 3: Reverse collected characters

   Since traversal is from end to start, collected characters must be reversed to get correct LCS.

4. Final Answer:

   Start from dp[m][n], move diagonally up-left if characters match, else move to the cell with the larger value, collecting matched characters in reverse order. -> Option B

5. Quick Check:

   Backtrack dp table from bottom-right to reconstruct LCS [OK]

Hint: Backtrack dp from bottom-right, collect matches, then reverse [OK]

Common Mistakes:

• Starting reconstruction from top-left
• Not reversing collected characters
• Ignoring dp values when moving