Longest Common Substring in DSA Go - Build from Scratch

Longest Common Substring

📖 Scenario: You are working on a text analysis tool that helps find the longest common substring between two given words. This can be useful in spell checkers, plagiarism detectors, or DNA sequence analysis.

🎯 Goal: Build a Go program that finds the longest common substring between two strings using dynamic programming.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D slice to store lengths of common substrings

Implement nested loops to fill the 2D slice based on character matches

Track the maximum length and ending index of the longest common substring

Print the longest common substring found

💡 Why This Matters

🌍 Real World

Finding longest common substrings is useful in text comparison tools, DNA sequence analysis, and plagiarism detection.

💼 Career

Understanding dynamic programming and string manipulation is important for software developers working on search engines, bioinformatics, and data analysis.

1

Create the input strings

Create two string variables called str1 and str2 with the exact values "ABABC" and "BABCA" respectively.

DSA Go

# Your code here

Hint

Use := to declare and assign the strings str1 and str2.

2

Initialize the 2D slice for dynamic programming

Create a 2D slice of integers called dp with dimensions len(str1)+1 by len(str2)+1. Initialize all values to zero. Also create two integer variables called maxLength and endIndex and set them to zero.

DSA Go

package main

func main() {
    str1 := "ABABC"
    str2 := "BABCA"
    // Your code here
}

Hint

Use make to create the 2D slice and initialize maxLength and endIndex to zero.

3

Fill the 2D slice and find the longest common substring

Use nested for loops with variables i from 1 to len(str1) and j from 1 to len(str2). Inside the inner loop, if str1[i-1] equals str2[j-1], set dp[i][j] to dp[i-1][j-1] + 1. If dp[i][j] is greater than maxLength, update maxLength to dp[i][j] and endIndex to i.

DSA Go

package main

func main() {
    str1 := "ABABC"
    str2 := "BABCA"

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

    maxLength := 0
    endIndex := 0

    // Your code here
}

Hint

Use nested loops and compare characters at i-1 and j-1. Update dp[i][j], maxLength, and endIndex accordingly.

4

Print the longest common substring

Print the substring of str1 starting from endIndex - maxLength up to endIndex using fmt.Println.

DSA Go

package main

import "fmt"

func main() {
    str1 := "ABABC"
    str2 := "BABCA"

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

    maxLength := 0
    endIndex := 0

    for i := 1; i  maxLength {
                    maxLength = dp[i][j]
                    endIndex = i
                }
            }
        }
    }

    // Your code here
}

Hint

Use slicing on str1 from endIndex - maxLength to endIndex and print it with fmt.Println.

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