Longest Common Substring in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Substring Length Calculation

What is the output of the following Go code that calculates the length of the longest common substring between two strings?

DSA Go

package main
import "fmt"
func longestCommonSubstring(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)
    }
    maxLen := 0
    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
                if dp[i][j] > maxLen {
                    maxLen = dp[i][j]
                }
            }
        }
    }
    return maxLen
}
func main() {
    fmt.Println(longestCommonSubstring("abcde", "abfce"))
}

A 2

B 3

C 4

D 1

💡 Hint

Check the longest sequence of matching characters in order.

The longest common substring between "abcde" and "abfce" is "ab" which has length 2.

🧠 Conceptual

intermediate

Understanding Longest Common Substring vs Longest Common Subsequence

Which statement correctly describes the difference between the longest common substring and the longest common subsequence?

A Longest common substring requires characters to be contiguous; subsequence does not.

B Longest common subsequence requires characters to be contiguous; substring does not.

C Both require characters to be contiguous in the original strings.

D Neither requires characters to be contiguous.

💡 Hint

Think about whether characters must be next to each other.

A substring is a continuous part of a string, while a subsequence can skip characters.

🔧 Debug

advanced

Identify the Error in Longest Common Substring Implementation

What error does the following Go code produce when run, and why? package main import "fmt" func longestCommonSubstring(s1, s2 string) int { m, n := len(s1), len(s2) dp := make([][]int, m) for i := range dp { dp[i] = make([]int, n) } maxLen := 0 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 if dp[i][j] > maxLen { maxLen = dp[i][j] } } } } return maxLen } func main() { fmt.Println(longestCommonSubstring("abc", "abc")) }

A returns 0 because dp array is not initialized

B compilation error due to missing import statement

C runtime error: index out of range because dp is sized m x n but accessed up to dp[m][n]

D infinite loop due to incorrect loop conditions

💡 Hint

Check how dp array is created and accessed.

The dp array is created with size m x n but the loops access dp[i][j] where i and j go up to m and n inclusive, causing out of range error.

🚀 Application

advanced

Longest Common Substring in DNA Sequences

Given two DNA sequences "AGCTTAGC" and "CTTAGGCA", what is the longest common substring?

A "AGC"

B "CTTAG"

C "TAGC"

D "GCTT"

💡 Hint

Look for the longest continuous matching segment.

"CTTAG" appears continuously in both sequences and is the longest common substring.

❓ Predict Output

expert

Output of Optimized Longest Common Substring Length Calculation

What is the output of this optimized Go code that calculates the length of the longest common substring?

DSA Go

package main
import "fmt"
func longestCommonSubstring(s1, s2 string) int {
    m, n := len(s1), len(s2)
    prev := make([]int, n+1)
    maxLen := 0
    for i := 1; i <= m; i++ {
        curr := make([]int, n+1)
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                curr[j] = prev[j-1] + 1
                if curr[j] > maxLen {
                    maxLen = curr[j]
                }
            }
        }
        prev = curr
    }
    return maxLen
}
func main() {
    fmt.Println(longestCommonSubstring("banana", "ananas"))
}

A 2

B 3

C 5

D 4

💡 Hint

Check the longest continuous matching substring between the two strings.

The longest common substring between "banana" and "ananas" is "anan" with length 4.

Practice

1. What does the Longest Common Substring problem find between two strings s1 and s2?

easy

A. The total count of common characters between the two strings

B. The longest sequence of characters that appear consecutively in both strings

C. The longest sequence of characters that appear in any order in both strings

D. The longest sequence of characters that appear only in the first string

Solution

1. Step 1: Understand the problem definition

   The Longest Common Substring problem looks for the longest sequence of characters that appear consecutively in both strings.

2. Step 2: Differentiate from similar problems

   Unlike subsequence problems, substring requires characters to be continuous and in the same order in both strings.

3. Final Answer:

   The longest sequence of characters that appear consecutively in both strings -> Option B

4. Quick Check:

   Longest Common Substring = consecutive matching characters [OK]

Hint: Look for continuous matching characters in both strings [OK]

Common Mistakes:

• Confusing substring with subsequence
• Thinking order does not matter
• Counting total common characters instead of longest sequence

2. Which of the following Go code snippets correctly initializes a 2D slice dp for Longest Common Substring of lengths m and n?

easy

A. dp := [][]int{{m+1}, {n+1}}

B. dp := make([]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}

C. var dp [m+1][n+1]int

D. dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}

Solution

1. Step 1: Understand Go slice initialization

   To create a 2D slice, first create the outer slice with length m+1, then initialize each inner slice with length n+1.

2. Step 2: Check each option

   dp := make([][]int, m+1) for i := range dp { dp[i] = make([]int, n+1) } correctly creates dp as [][]int with proper inner slices. dp := make([]int, m+1) for i := range dp { dp[i] = make([]int, n+1) } tries to assign inner slices to int slice, invalid. var dp [m+1][n+1]int uses array syntax but m,n are variables, so invalid. dp := [][]int{{m+1}, {n+1}} creates a slice with two elements, not a 2D slice.

3. Final Answer:

   dp := make([][]int, m+1) for i := range dp { dp[i] = make([]int, n+1) } -> Option D

4. Quick Check:

   Proper 2D slice initialization = dp := make([][]int, m+1) for i := range dp { dp[i] = make([]int, n+1) } [OK]

Hint: Use make for outer slice, then loop to make inner slices [OK]

Common Mistakes:

• Using make for inner slices on a 1D int slice
• Trying to declare arrays with variable sizes
• Incorrect slice literal syntax

3. What is the output of the following Go code that finds the length of the longest common substring between s1 = "abcde" and s2 = "abfde"?

func longestCommonSubstring(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)
  }
  maxLen := 0
  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
        if dp[i][j] > maxLen {
          maxLen = dp[i][j]
        }
      }
    }
  }
  return maxLen
}

fmt.Println(longestCommonSubstring("abcde", "abfde"))

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Trace matching characters

   Compare characters of "abcde" and "abfde": - 'a' == 'a' (dp[1][1] = 1) - 'b' == 'b' (dp[2][2] = 2) - 'c' != 'f' (reset) - 'd' == 'd' (dp[4][4] = 1) - 'e' == 'e' (dp[5][5] = 2)

2. Step 2: Find longest continuous match

   The longest continuous matches are "ab" (length 2) and "de" (length 2). No longer sequence exists. Thus, maxLen = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest common substring length = 2 [OK]

Hint: Check character by character and track max continuous matches [OK]

Common Mistakes:

• Counting non-continuous matches
• Confusing substring length with subsequence length
• Off-by-one errors in indexing

4. The following Go code attempts to find the longest common substring length but has a bug. What is the bug?

func longestCommonSubstring(s1, s2 string) int {
  m, n := len(s1), len(s2)
  dp := make([][]int, m)
  for i := range dp {
    dp[i] = make([]int, n)
  }
  maxLen := 0
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if s1[i] == s2[j] {
        dp[i][j] = dp[i-1][j-1] + 1
        if dp[i][j] > maxLen {
          maxLen = dp[i][j]
        }
      }
    }
  }
  return maxLen
}

medium

A. The condition should use '!=' instead of '=='

B. The loops should start from 1 instead of 0

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

D. maxLen should be initialized to 1

Solution

1. Step 1: Analyze dp slice size

   The dp slice is created with size m and n, but the code accesses dp[i-1][j-1] which can cause index out of range when i or j is 0.

2. Step 2: Correct dp dimensions

   To safely access dp[i-1][j-1], dp should be sized (m+1) x (n+1) and loops should run from 1 to m and n, avoiding negative indices.

3. Final Answer:

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

4. Quick Check:

   dp size must allow safe dp[i-1][j-1] access [OK]

Hint: Use dp size m+1 and n+1 to avoid negative indices [OK]

Common Mistakes:

• Using dp size m and n causing index errors
• Starting loops at 0 causing negative index access
• Incorrect initialization of maxLen

5. Given two strings s1 = "ababc" and s2 = "babca", write a Go function to find the longest common substring and return the substring itself (not just length). What will be the returned substring?

hard

A. "babc"

B. "ababc"

C. "babc" or "abca" depending on implementation

D. "abca"

Solution

1. Step 1: Identify longest common substrings

   Check substrings common to both: - "ababc" vs "babca" share "babc" as longest common substring of length 4. - "abca" is not a substring of s1. - "babc" appears in both strings consecutively.

2. Step 2: Confirm substring returned

   The longest common substring is "babc" with length 4, so the function should return "babc".

3. Final Answer:

   "babc" -> Option A

4. Quick Check:

   Longest common substring = "babc" [OK]

Hint: Find longest continuous matching substring, return that string [OK]

Common Mistakes:

• Returning longest common subsequence instead
• Confusing substring with subsequence
• Returning multiple substrings instead of one