Longest Common Subsequence in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LCS length calculation

What is the output of this Go code that calculates the length of the Longest Common Subsequence (LCS) between two strings?

DSA Go

package main
import "fmt"
func lcsLength(a, b string) int {
    m, n := len(a), len(b)
    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 a[i-1] == b[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() {
    a := "AGGTAB"
    b := "GXTXAYB"
    fmt.Println(lcsLength(a, b))
}

A 4

B 3

C 6

D 5

💡 Hint

Trace the matching characters between the two strings and count the longest sequence.

The longest common subsequence between "AGGTAB" and "GXTXAYB" is "GTAB" which has length 4.

❓ Predict Output

intermediate

Output of LCS sequence reconstruction

What is the output of this Go code that reconstructs and prints the Longest Common Subsequence (LCS) string between two strings?

DSA Go

package main
import "fmt"
func lcsSequence(a, b string) string {
    m, n := len(a), len(b)
    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 a[i-1] == b[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]
                }
            }
        }
    }
    i, j := m, n
    lcs := []byte{}
    for i > 0 && j > 0 {
        if a[i-1] == b[j-1] {
            lcs = append([]byte{a[i-1]}, lcs...)
            i--
            j--
        } else if dp[i-1][j] > dp[i][j-1] {
            i--
        } else {
            j--
        }
    }
    return string(lcs)
}
func main() {
    a := "ABCBDAB"
    b := "BDCABA"
    fmt.Println(lcsSequence(a, b))
}

A BCBA

B BDAB

C BCAB

D BDCB

💡 Hint

Follow the dp table backwards to find matching characters.

The longest common subsequence between "ABCBDAB" and "BDCABA" is "BDAB".

The code reconstructs this sequence by moving backwards through the dp table.

🔧 Debug

advanced

Identify the bug in LCS length calculation

This Go code is intended to calculate the length of the Longest Common Subsequence (LCS) between two strings. What is the bug causing incorrect results?

DSA Go

package main
import "fmt"
func lcsLength(a, b string) int {
    m, n := len(a), len(b)
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if a[i] == b[j] {
                if i > 0 && j > 0 {
                    dp[i][j] = dp[i-1][j-1] + 1
                } else {
                    dp[i][j] = 1
                }
            } else {
                if i > 0 && j > 0 {
                    if dp[i-1][j] > dp[i][j-1] {
                        dp[i][j] = dp[i-1][j]
                    } else {
                        dp[i][j] = dp[i][j-1]
                    }
                } else if i > 0 {
                    dp[i][j] = dp[i-1][j]
                } else if j > 0 {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    return dp[m-1][n-1]
}
func main() {
    a := "ABC"
    b := "AC"
    fmt.Println(lcsLength(a, b))
}

A The code does not initialize dp[0][0] causing zero result

B The code does not handle the case when i or j is zero properly

C dp slice dimensions should be m+1 and n+1 to avoid index errors

D The code incorrectly compares characters at i and j instead of i-1 and j-1

💡 Hint

Check how dp array is sized and accessed with indices.

The dp array should have size (m+1) x (n+1) to safely access dp[i-1][j-1] when i or j is 1.

Current code uses m x n which causes index out of range or incorrect values.

🧠 Conceptual

advanced

Time complexity of LCS dynamic programming solution

What is the time complexity of the standard dynamic programming solution to find the Longest Common Subsequence (LCS) of two strings of lengths m and n?

A O(m * n)

B O(m + n)

C O(m^2 + n^2)

D O(2^(m+n))

💡 Hint

Consider the nested loops over both strings.

The standard DP solution uses a 2D table of size m by n and fills each cell once.

Thus, time complexity is O(m * n).

🚀 Application

expert

Number of distinct LCS sequences

Given two strings, the code below calculates the number of distinct Longest Common Subsequences (LCS) they have. What is the output of this code for strings "ABCBDAB" and "BDCABA"?

DSA Go

package main
import "fmt"
func countLCS(a, b string) int {
    m, n := len(a), len(b)
    dp := make([][]int, m+1)
    count := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        count[i] = make([]int, n+1)
        for j := range count[i] {
            count[i][j] = 1
        }
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
                count[i][j] = count[i-1][j-1]
            } else {
                if dp[i-1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i-1][j]
                    count[i][j] = count[i-1][j]
                } else if dp[i][j-1] > dp[i-1][j] {
                    dp[i][j] = dp[i][j-1]
                    count[i][j] = count[i][j-1]
                } else {
                    dp[i][j] = dp[i-1][j]
                    count[i][j] = count[i-1][j] + count[i][j-1]
                }
            }
        }
    }
    return count[m][n]
}
func main() {
    a := "ABCBDAB"
    b := "BDCABA"
    fmt.Println(countLCS(a, b))
}

A 6

B 4

C 3

D 5

💡 Hint

Count how many different sequences have the maximum length.

The longest common subsequence length is 4.

There are 5 distinct LCS sequences of length 4 between "ABCBDAB" and "BDCABA".

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