Longest Common Substring in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the 2D slice for dynamic programming.

DSA Go

dp := make([][]int, len(s1)+1)
for i := range dp {
    dp[i] = make([]int, [1])
}

Drag options to blanks, or click blank then click option'

Alen(s2)+1

Blen(s1)

Clen(s2)

Dlen(s1)+1

Attempts:

3 left

💡 Hint

Common Mistakes

Using length of s1 for both dimensions causes index errors.

Forgetting the +1 for base case initialization.

We create a 2D slice with rows for s1 and columns for s2 plus one extra for base case.

2fill in blank

medium

Complete the code to update the dp table when characters match.

DSA Go

if s1[i-1] == s2[j-1] {
    dp[i][j] = dp[i-1][[1]] + 1
}

Drag options to blanks, or click blank then click option'

Aj

Bi-1

Ci

Dj-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp[i-1][j] or dp[i][j-1] instead of dp[i-1][j-1].

Mixing up i and j indices.

When characters match, we extend the substring by 1 from the previous diagonal cell dp[i-1][j-1].

3fill in blank

hard

Fix the error in updating the maximum length of the common substring.

DSA Go

if dp[i][j] > [1] {
    maxLen = dp[i][j]
    endIndex = i
}

Drag options to blanks, or click blank then click option'

Ai

BendIndex

CmaxLen

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with endIndex instead of maxLen.

Updating endIndex incorrectly.

We compare dp[i][j] with maxLen to update the maximum length found so far.

4fill in blank

hard

Fill both blanks to extract the longest common substring from s1.

DSA Go

result := s1[[1]:[2]]

Drag options to blanks, or click blank then click option'

AendIndex - maxLen

BendIndex

CmaxLen

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using maxLen as the end index instead of endIndex.

Incorrect start index calculation.

The substring starts at endIndex - maxLen and ends at endIndex (exclusive).

5fill in blank

hard

Fill all three blanks to complete the nested loops for filling dp table.

DSA Go

for i := 1; i <= len(s1); i++ {
    for j := 1; j <= [1]; j++ {
        if s1[i-1] == s2[j-1] {
            dp[i][j] = dp[i-1][[2]] + 1
            if dp[i][j] > maxLen {
                maxLen = dp[i][j]
                endIndex = i
            }
        } else {
            dp[i][j] = [3]
        }
    }
}

Drag options to blanks, or click blank then click option'

Alen(s2)

Bj-1

C0

Dlen(s1)

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop limits causing index errors.

Incorrect dp reset value causing wrong results.

The inner loop runs over s2 length. We use dp[i-1][j-1] for previous diagonal. When no match, dp[i][j] is 0.

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