Longest Common Substring in DSA Go

Mental Model

Find the longest sequence of characters that appears exactly the same in both strings without skipping any characters.

Analogy: Imagine two friends reading two different books and trying to find the longest exact sentence that appears in both books without any changes or breaks.

String1: a b c d e f g
String2: x y b c d z
Longest common substring: b c d

Dry Run Walkthrough

Input: string1: "abcde", string2: "abfde"

Goal: Find the longest substring that appears in both strings exactly.

Step 1: Compare characters at string1[0] and string2[0]

a == a -> current length = 1

Why: Start matching from the first characters to find common substrings.

Step 2: Compare string1[1] and string2[1]

b == b -> current length = 2

Why: Continue matching consecutive characters to extend the substring.

Step 3: Compare string1[2] and string2[2]

c != f -> reset current length to 0

Why: Mismatch breaks the substring, so start fresh from next positions.

Step 4: Compare string1[3] and string2[3]

d == d -> current length = 1

Why: Found a new matching character, start counting new substring length.

Step 5: Compare string1[4] and string2[4]

e == e -> current length = 2

Why: Extend the new substring with matching characters.

Result:

Longest common substring length = 2, substring example: "ab"

Annotated Code

DSA Go

package main

import "fmt"

func longestCommonSubstring(s1, s2 string) (int, string) {
	m, n := len(s1), len(s2)
	// Create a 2D slice to store lengths of common suffixes
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	maxLen := 0
	endIndex := 0

	// Build dp table
	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 // extend previous substring
				if dp[i][j] > maxLen {
					maxLen = dp[i][j] // update max length
					endIndex = i // mark end index of substring in s1
				}
			} else {
				dp[i][j] = 0 // reset on mismatch
			}
		}
	}

	// Extract substring from s1 using endIndex and maxLen
	return maxLen, s1[endIndex-maxLen : endIndex]
}

func main() {
	length, substring := longestCommonSubstring("abcde", "abfde")
	fmt.Printf("Longest common substring length: %d\n", length)
	fmt.Printf("Longest common substring: %s\n", substring)
}

if s1[i-1] == s2[j-1] {

Check if characters match to extend substring length

dp[i][j] = dp[i-1][j-1] + 1

Extend length of common substring ending at these positions

if dp[i][j] > maxLen {

Update max length and end index if longer substring found

dp[i][j] = 0

Reset length on mismatch

Output

Longest common substring length: 2

Longest common substring: ab

Complexity Analysis

Time: O(m*n) because we compare each character of string1 with each character of string2 once

Space: O(m*n) because we store lengths of common substrings for all pairs of positions

vs Alternative: Naive approach checks all substrings which is O(m^2*n^2), so DP is much faster

Edge Cases

One or both strings empty

Returns length 0 and empty substring

DSA Go

dp[i][j] = 0 // reset on mismatch

No common substring

Returns length 0 and empty substring

DSA Go

dp[i][j] = 0 // reset on mismatch

Strings are identical

Returns full length and the entire string

DSA Go

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

When to Use This Pattern

When asked to find the longest exact matching sequence inside two strings, use the longest common substring pattern with dynamic programming to efficiently track matching suffix lengths.

Common Mistakes

Mistake: Confusing longest common substring with longest common subsequence which allows skipping characters
Fix: Remember substring requires consecutive characters; use DP table that resets on mismatch

Mistake: Not updating max length and end index correctly when a longer substring is found
Fix: Update maxLen and endIndex inside the nested loops whenever dp[i][j] exceeds current maxLen

Summary

Finds the longest consecutive matching substring between two strings.

Use when you need the longest exact sequence shared by both strings without gaps.

Track lengths of matching suffixes with a 2D table and reset on mismatches.

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