Longest Common Subsequence in DSA Go - Execution Trace

Concept Flow - Longest Common Subsequence

Start with two strings

↓

Create DP table with size (len(s1)+1) x (len(s2)+1)

↓

Fill DP table row by row

↓

For each cell: compare characters

↓

i

↓

i

↓

DP table filled

↓

Backtrack from dp[len(s1)

↓

Output LCS length and sequence

↓

Done

We build a table comparing prefixes of two strings, filling it based on character matches or max subsequence length, then backtrack to find the longest common subsequence.

Execution Sample

DSA Go

s1 := "ABCBDAB"
s2 := "BDCABA"
// Build dp table and find LCS length and sequence

This code finds the longest common subsequence between "ABCBDAB" and "BDCABA" using dynamic programming.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Cell Value	DP Table State (partial)
1	Initialize DP table with zeros	-	-	-	[All zeros]
2	Compare s1[1]='A' and s2[1]='B'	(1,1)	'A' vs 'B'	0	[[0,0,0,0,0,0,0],[0,0,...]]
3	Compare s1[1]='A' and s2[2]='D'	(1,2)	'A' vs 'D'	0	[[0,0,0,0,0,0,0],[0,0,0,...]]
4	Compare s1[1]='A' and s2[3]='C'	(1,3)	'A' vs 'C'	0	[[0,0,0,0,0,0,0],[0,0,0,0,...]]
5	Compare s1[1]='A' and s2[4]='A'	(1,4)	'A' vs 'A'	1	[[0,0,0,0,0,0,0],[0,0,0,0,1,...]]
6	Compare s1[1]='A' and s2[5]='B'	(1,5)	'A' vs 'B'	1	[[0,0,0,0,0,0,0],[0,0,0,0,1,1,...]]
7	Compare s1[1]='A' and s2[6]='A'	(1,6)	'A' vs 'A'	1	[[0,0,0,0,0,0,0],[0,0,0,0,1,1,1]]
8	Compare s1[2]='B' and s2[1]='B'	(2,1)	'B' vs 'B'	1	[[0,0,0,0,0,0,0],[0,0,0,0,1,1,1],[0,1,...]]
9	Compare s1[2]='B' and s2[2]='D'	(2,2)	'B' vs 'D'	1	[...,[0,1,1,...]]
10	Compare s1[2]='B' and s2[3]='C'	(2,3)	'B' vs 'C'	1	[...,[0,1,1,1,...]]
11	Compare s1[2]='B' and s2[4]='A'	(2,4)	'B' vs 'A'	1	[...,[0,1,1,1,1,...]]
12	Compare s1[2]='B' and s2[5]='B'	(2,5)	'B' vs 'B'	2	[...,[0,1,1,1,1,2,...]]
13	Compare s1[2]='B' and s2[6]='A'	(2,6)	'B' vs 'A'	2	[...,[0,1,1,1,1,2,2]]
14	Continue filling DP table similarly for all i,j	-	-	-	[DP table gradually fills]
15	DP table fully filled	(7,6)	-	4	[Final DP table with LCS length 4]
16	Backtrack to find LCS sequence	-	-	-	LCS = 'BCAB'
17	Output LCS length and sequence	-	-	-	Length=4, Sequence='BCAB'
18	End	-	-	-	Done

💡 DP table fully filled and LCS sequence found by backtracking

Variable Tracker

Variable	Start	After Step 5	After Step 12	After Step 15	Final
i	0	1	2	7	7
j	0	4	5	6	6
dp[i][j]	0	1 (at 1,4)	2 (at 2,5)	4 (at 7,6)	4 (final)
LCS sequence	""	""	""	""	"BCAB"

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 5 where dp[1][4] = dp[0][3] + 1 = 1.

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

Because the longest subsequence up to this point is the best from either skipping a character in s1 or s2, as seen in steps 2-4 where no match leads to dp cell value 0.

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

We backtrack from dp[len(s1)][len(s2)] following matches and max values, as in step 16 where the sequence 'BCAB' is reconstructed.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the dp cell value and why?

A 0, because characters do not match

B 1, because characters match and we add 1 to dp[i-1][j-1]

C 2, because we take max of neighbors

D Undefined, dp not filled yet

💡 Hint

Refer to execution_table row with Step 5 comparing 'A' and 'A' and dp cell value

At which step does the DP table first record a value of 2?

A Step 7

B Step 12

C Step 15

D Step 18

💡 Hint

Check execution_table rows for dp cell values, step 12 shows dp[i][j] = 2

If the first characters of s1 and s2 were the same, how would the DP table change at step 2?

A dp[1][1] would be 1 instead of 0

B dp[1][1] would remain 0

C dp[1][1] would be 2

D No change in dp table

💡 Hint

Look at how dp[i][j] updates when characters match, as in step 5

Concept Snapshot

Longest Common Subsequence (LCS):
- Use 2D DP table of size (len(s1)+1) x (len(s2)+1)
- dp[i][j] = length of LCS of s1[:i] and s2[: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 from dp[len(s1)][len(s2)] to get LCS string
- Time complexity: O(m*n), m,n = lengths of strings

Full Transcript

Longest Common Subsequence (LCS) finds the longest sequence present in both strings in order. We create a table where each cell dp[i][j] stores the length of LCS for prefixes s1 up to i and s2 up to j. We fill this table by comparing characters: if they match, we add 1 to the diagonal cell; if not, we take the maximum from left or top cells. After filling the table, we backtrack from the bottom-right cell to reconstruct the LCS string. This method ensures we find the longest common subsequence efficiently.

Practice

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

easy

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

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

C. The shortest sequence that can be formed by combining both strings.

D. The total number of characters in both strings combined.

Solution

1. Step 1: Understand the definition of LCS

   The LCS is the longest sequence that appears in both strings in the same order, but characters do not need to be next to each other.

2. Step 2: Differentiate from substring

   A substring requires characters to be consecutive, but LCS allows gaps.

3. Final Answer:

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

4. Quick Check:

   LCS = longest ordered sequence [OK]

Hint: LCS is about order, not consecutive characters [OK]

Common Mistakes:

• Confusing LCS with longest substring
• Thinking LCS characters must be consecutive
• Mixing LCS with string concatenation

2. Which of the following Go function signatures correctly represents a function to compute the length of the LCS of two strings s1 and s2?

easy

A. func lcs(s1, s2 string) int

B. func lcs(s1, s2 int) string

C. func lcs(s1, s2 []int) int

D. func lcs(s1, s2 string) string

Solution

1. Step 1: Identify input types for LCS function

   The LCS function takes two strings as input, so parameters should be of type string.

2. Step 2: Identify output type for LCS function

   The function returns the length of the LCS, which is an integer.

3. Final Answer:

   func lcs(s1, s2 string) int -> Option A

4. Quick Check:

   Input strings, output int length [OK]

Hint: LCS inputs are strings, output is integer length [OK]

Common Mistakes:

• Using wrong input types like int or slices
• Returning string instead of length
• Mixing input and output types

3. What is the output of the following Go code snippet?

package main
import "fmt"
func lcs(s1, s2 string) int {
    m, n := len(s1), len(s2)
    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 s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                if dp[i-1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i-1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    return dp[m][n]
}
func main() {
    fmt.Println(lcs("AGGTAB", "GXTXAYB"))
}

medium

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Understand the input strings

   Strings are "AGGTAB" and "GXTXAYB". We find their LCS length using dynamic programming.

2. Step 2: Trace the LCS calculation

   The LCS is "GTAB" which has length 4, but checking carefully the code and strings, the LCS is actually "GTAB" (length 4) or "GTTAB"? The correct LCS is "GTAB" length 4 or "GTAB" length 4? Actually, the LCS is "GTAB" length 4. But the code returns 4 or 5? Let's check carefully: The LCS is "GTAB" (G T A B) length 4. But the code returns dp[m][n], which is 4. But options have 4 and 5. Let's verify carefully: The LCS is "GTAB" length 4. So output is 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

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

Hint: Trace DP table or recall classic LCS example [OK]

Common Mistakes:

• Confusing LCS length with longest substring length
• Off-by-one errors in indexing
• Misreading input strings

4. The following Go code attempts to compute the LCS length but has a bug. What is the bug?

func lcs(s1, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    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 {
                if dp[i-1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i-1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    return dp[m-1][n-1]
}

medium

A. The return statement should be dp[m][n] instead of dp[m-1][n-1].

B. The loops should start from 0 instead of 1.

C. The dp slice is not initialized with size m+1 and n+1, causing index out of range errors.

D. The comparison s1[i-1] == s2[j-1] should be s1[i] == s2[j].

Solution

1. Step 1: Check dp slice initialization

   The dp slice is created with size m and n, but the loops access dp[i][j] for i and j up to m and n inclusive, causing index out of range errors.

2. Step 2: Correct dp size for safe indexing

   dp should be initialized with size m+1 and n+1 to safely access dp[i][j] where i and j go up to m and n.

3. Final Answer:

   The dp slice is not initialized with size m+1 and n+1, causing index out of range errors. -> Option C

4. Quick Check:

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

Hint: dp size must cover all indices used in loops [OK]

Common Mistakes:

• Initializing dp with size m and n instead of m+1 and n+1
• Starting loops at 1 but dp size too small
• Incorrect return index

5. Given two strings s1 = "ABCBDAB" and s2 = "BDCABA", write a Go function that returns the actual Longest Common Subsequence string, not just its length. Which approach correctly reconstructs the LCS from the DP table?

hard

A. Sort both strings and find common characters in sorted order.

B. Build the DP table and return dp[m][n] as the LCS string directly.

C. Use recursion without memoization to find the LCS string.

D. Build the DP table for LCS length, then backtrack from dp[m][n] moving diagonally when characters match, else move in direction of larger dp value.

Solution

1. Step 1: Build DP table for LCS length

   Use dynamic programming to fill dp table with lengths of LCS for substrings of s1 and s2.

2. Step 2: Backtrack to reconstruct LCS string

   Start from dp[m][n], move diagonally up-left if characters match (add character to result), else move in direction of larger dp value until reaching dp[0][0].

3. Final Answer:

   Build the DP table for LCS length, then backtrack from dp[m][n] moving diagonally when characters match, else move in direction of larger dp value. -> Option D

4. Quick Check:

   DP + backtracking reconstructs LCS string [OK]

Hint: Backtrack DP table diagonally on matches to get LCS string [OK]

Common Mistakes:

• Returning dp[m][n] as string instead of length
• Not backtracking to reconstruct sequence
• Sorting strings loses original order