Longest Common Substring in DSA Go - Execution Trace

Concept Flow - Longest Common Substring

Start with two strings

↓

Create 2D table of size (len(s1)+1) x (len(s2)+1)

↓

Initialize all cells to 0

↓

For each character in s1 (i)

↓

For each character in s2 (j)

↓

If s1[i-1

Yes↓

Set table[i

↓

Update max length and end position if needed

↓

Else

No↓

Set table[i

↓

After filling table, extract substring from s1 using max length and end position

↓

Return longest common substring

↓

Done

We build a table to track matching characters between two strings. When characters match, we extend the substring length. We keep track of the longest match and extract it at the end.

Execution Sample

DSA Go

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

This code finds the longest substring common to both s1 and s2 by building a 2D table of substring lengths. (Example: s1="abc", s2="bac")

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	Table Update	Max Length	End Position	Visual State
1	Initialize dp table	-	-	All zeros	0	0	[[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]
2	Compare s1[0] and s2[0]	(1,1)	'a' vs 'b'	dp[1][1] = 0	0	0	[[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]
3	Compare s1[0] and s2[1]	(1,2)	'a' vs 'a'	dp[1][2] = dp[0][1] + 1 = 1	1	1	[[0 0 0 0] [0 0 1 0] [0 0 0 0] [0 0 0 0]]
4	Compare s1[0] and s2[2]	(1,3)	'a' vs 'c'	dp[1][3] = 0	1	1	[[0 0 0 0] [0 0 1 0] [0 0 0 0] [0 0 0 0]]
5	Compare s1[1] and s2[0]	(2,1)	'b' vs 'b'	dp[2][1] = dp[1][0] + 1 = 1	1	2	[[0 0 0 0] [0 0 1 0] [1 0 0 0] [0 0 0 0]]
6	Compare s1[1] and s2[1]	(2,2)	'b' vs 'a'	dp[2][2] = 0	1	2	[[0 0 0 0] [0 0 1 0] [1 0 0 0] [0 0 0 0]]
7	Compare s1[1] and s2[2]	(2,3)	'b' vs 'c'	dp[2][3] = 0	1	2	[[0 0 0 0] [0 0 1 0] [1 0 0 0] [0 0 0 0]]
8	Compare s1[2] and s2[0]	(3,1)	'c' vs 'b'	dp[3][1] = 0	1	2	[[0 0 0 0] [0 0 1 0] [1 0 0 0] [0 0 0 0]]
9	Compare s1[2] and s2[1]	(3,2)	'c' vs 'a'	dp[3][2] = 0	1	2	[[0 0 0 0] [0 0 1 0] [1 0 0 0] [0 0 0 0]]
10	Compare s1[2] and s2[2]	(3,3)	'c' vs 'c'	dp[3][3] = dp[2][2] + 1 = 1	1	3	[[0 0 0 0] [0 0 1 0] [1 0 0 0] [0 0 0 1]]
11	End loops	-	-	-	1	3	Longest substring length 1 at position 3 in s1
12	Extract substring	-	-	-	-	-	Substring: s1[3-1:3] = 'c'

💡 All characters compared; longest substring length found and extracted.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 10	Final
maxLen	0	1	1	1	1
end	0	1	2	3	3
dp[1][2]	0	1	1	1	1
dp[2][1]	0	0	1	1	1
dp[3][3]	0	0	0	1	1

Key Moments - 3 Insights

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

Because dp[i-1][j-1] stores the length of the common substring ending at previous characters. Adding 1 extends that substring by one matching character (see steps 3, 5, 10 in execution_table).

Why do we set dp[i][j] to 0 when characters don't match?

Because the substring must be continuous. A mismatch breaks the substring, so length resets to 0 at that position (see steps 2, 4, 6, 7, 8, 9).

How do we know where the longest substring ends in s1?

We track the 'end' variable whenever we find a longer substring or an equal length one later (see steps 3, 5, 10).

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the value of dp[1][2] after this step?

A 2

B 0

C 1

D Undefined

💡 Hint

Check the 'Table Update' column at step 3 in execution_table.

At which step does the maxLen first update to 1?

A Step 2

B Step 3

C Step 5

D Step 10

💡 Hint

Look at the 'Max Length' column in execution_table and find when it changes from 0 to 1.

If the characters at s1[2] and s2[2] did not match, what would dp[3][3] be after step 10?

A 0

B 1

C 2

D Undefined

💡 Hint

Refer to the rule that sets dp[i][j] to 0 when characters don't match (see steps 4, 6, 7).

Concept Snapshot

Longest Common Substring:
- Use 2D table dp with size (len(s1)+1) x (len(s2)+1)
- dp[i][j] = length of longest common substring ending at s1[i-1], s2[j-1]
- If chars match: dp[i][j] = dp[i-1][j-1] + 1
- Else: dp[i][j] = 0
- Track max length and end position
- Extract substring from s1[end-maxLen:end]

Full Transcript

Longest Common Substring finds the longest continuous matching substring between two strings. We create a 2D table where each cell dp[i][j] stores the length of the longest common substring ending at s1[i-1] and s2[j-1]. We fill the table by comparing characters. If they match, we extend the substring length by adding 1 to dp[i-1][j-1]. If not, we reset to 0 because the substring must be continuous. We keep track of the maximum length found and the position where it ends in s1. After filling the table, we extract the substring from s1 using the recorded end position and max length. This method efficiently finds the longest common substring in O(m*n) time, where m and n are the lengths of the input strings.

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