Find Longest Common Substring in Two Strings

Given two strings s1 and s2, your task is to find the longest common substring shared between them.

• A common substring is a sequence of characters that appears consecutively in both strings.
• Return the length of the longest such substring.
• If no common substring exists, return 0.

This problem is widely used to test your understanding of dynamic programming, particularly with 2D table approaches for string comparison.

Understanding the Problem

We are given two strings: s1 and s2. Our goal is to find the longest common substring shared between them.

A substring means characters must be consecutive and appear in the same order in both strings.

For example, in s1 = "abcde" and s2 = "abfce", the common substrings are "a", "b", and "e". The longest among them is of length 1.

Step-by-Step Solution with Example

Step 1: Choose a strategy

We'll use a technique called Dynamic Programming. It helps us solve problems by breaking them down into smaller overlapping subproblems and storing their solutions.

Step 2: Initialize a 2D array

We create a 2D array dp where dp[i][j] represents the length of the longest common substring ending at s1[i-1] and s2[j-1].

This array has dimensions (len(s1)+1) x (len(s2)+1), and we initialize it with 0s.

Step 3: Define variables to track the result

We keep:

• maxLen = 0 – to store the length of the longest substring found so far
• endIndex = 0 – to remember where that substring ends in s1

Step 4: Loop through characters of both strings

We loop through i from 1 to len(s1), and inside that, loop through j from 1 to len(s2).

Step 5: Compare characters

If s1[i-1] == s2[j-1], it means we can extend the previous matching substring, so we do:

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

Step 6: Update the maximum length and position

If this newly found substring is longer than any previous one, update maxLen and endIndex:

if dp[i][j] > maxLen:
    maxLen = dp[i][j]
    endIndex = i

Step 7: Extract the final result

Once we've filled the dp table, we extract the substring from s1:

longest_substring = s1[endIndex - maxLen : endIndex]

Example:

s1 = "abcdf", s2 = "abedf"

The common substrings are "ab" and "df". The longest is "ab" (length 2).

The 2D dp table helps track where the substrings match and how long they are.

Edge Cases

• Empty strings: If either s1 or s2 is empty, return 0.
• No common substring: If no characters match consecutively, return 0.
• Full match: If the strings are identical, return the full string as the result.
• Multiple same-length substrings: Return any one of them (most implementations return the one that appears first in s1).

1. Create a 2D array dp of size (len(s1)+1) x (len(s2)+1), initialized with 0. This will store lengths of common suffixes.
2. Initialize two variables: maxLen = 0 to track the length of the longest common substring, and endIndex = 0 to remember its ending index in s1.
3. Loop through i from 1 to len(s1):
4. For each i, loop through j from 1 to len(s2):
5. If s1[i-1] == s2[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
6. If dp[i][j] > maxLen, update maxLen and set endIndex = i.
7. After processing, return s1[endIndex - maxLen : endIndex] as the longest common substring.

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    end_index = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_index = i
    return s1[end_index - max_len:end_index]

# Example usage
s1 = "abcde"
s2 = "abfce"
print(longest_common_substring(s1, s2))  # Output: "abc"

public class LongestCommonSubstring {
    public static String longestCommonSubstring(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        int maxLen = 0;
        int endIndex = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        endIndex = i;
                    }
                }
            }
        }
        return s1.substring(endIndex - maxLen, endIndex);
    }

    public static void main(String[] args) {
        String s1 = "abcde";
        String s2 = "abfce";
        System.out.println(longestCommonSubstring(s1, s2)); // Output: "abc"
    }
}

function longestCommonSubstring(s1, s2) {
  const m = s1.length;
  const n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  let maxLen = 0;
  let endIndex = 0;

  for (let i = 1; i <= m; i++) {
    for (let 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];
          endIndex = i;
        }
      }
    }
  }
  return s1.slice(endIndex - maxLen, endIndex);
}

// Example usage
console.log(longestCommonSubstring("abcde", "abfce")); // Output: "abc"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* longestCommonSubstring(const char* s1, const char* s2) {
    int m = strlen(s1);
    int n = strlen(s2);
    int** dp = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int*)calloc(n + 1, sizeof(int));
    }
    int maxLen = 0;
    int endIndex = 0;

    for (int i = 1; i <= m; i++) {
        for (int 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];
                    endIndex = i;
                }
            }
        }
    }

    char* result = (char*)malloc((maxLen + 1) * sizeof(char));
    strncpy(result, s1 + endIndex - maxLen, maxLen);
    result[maxLen] = '\0';

    for (int i = 0; i <= m; i++) free(dp[i]);
    free(dp);

    return result;
}

int main() {
    const char* s1 = "abcde";
    const char* s2 = "abfce";
    char* res = longestCommonSubstring(s1, s2);
    printf("%s\n", res);  // Output: abc
    free(res);
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string longestCommonSubstring(const string& s1, const string& s2) {
    int m = s1.size();
    int n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int maxLen = 0, endIndex = 0;

    for (int i = 1; i <= m; i++) {
        for (int 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];
                    endIndex = i;
                }
            }
        }
    }
    return s1.substr(endIndex - maxLen, maxLen);
}

int main() {
    string s1 = "abcde";
    string s2 = "abfce";
    cout << longestCommonSubstring(s1, s2) << endl;  // Output: abc
    return 0;
}

package main

import "fmt"

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, endIndex := 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]
                    endIndex = i
                }
            }
        }
    }
    return s1[endIndex-maxLen : endIndex]
}

func main() {
    s1 := "abcde"
    s2 := "abfce"
    fmt.Println(longestCommonSubstring(s1, s2)) // Output: abc
}

fn longest_common_substring(s1: &str, s2: &str) -> &str {
    let m = s1.len();
    let n = s2.len();
    let s1_bytes = s1.as_bytes();
    let s2_bytes = s2.as_bytes();
    let mut dp = vec![vec![0; n + 1]; m + 1];
    let mut max_len = 0;
    let mut end_index = 0;

    for i in 1..=m {
        for j in 1..=n {
            if s1_bytes[i - 1] == s2_bytes[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if dp[i][j] > max_len {
                    max_len = dp[i][j];
                    end_index = i;
                }
            }
        }
    }

    &s1[end_index - max_len..end_index]
}

fn main() {
    let s1 = "abcde";
    let s2 = "abfce";
    println!("{}", longest_common_substring(s1, s2)); // Output: abc
}

fun longestCommonSubstring(s1: String, s2: String): String {
    val m = s1.length
    val n = s2.length
    val dp = Array(m + 1) { IntArray(n + 1) }
    var maxLen = 0
    var endIndex = 0

    for (i in 1..m) {
        for (j in 1..n) {
            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]
                    endIndex = i
                }
            }
        }
    }
    return s1.substring(endIndex - maxLen, endIndex)
}

fun main() {
    val s1 = "abcde"
    val s2 = "abfce"
    println(longestCommonSubstring(s1, s2)) // Output: abc
}

func longestCommonSubstring(_ s1: String, _ s2: String) -> String {
    let m = s1.count
    let n = s2.count
    let s1Array = Array(s1)
    let s2Array = Array(s2)
    var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
    var maxLen = 0
    var endIndex = 0

    for i in 1...m {
        for j in 1...n {
            if s1Array[i - 1] == s2Array[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > maxLen {
                    maxLen = dp[i][j]
                    endIndex = i
                }
            }
        }
    }
    return String(s1Array[(endIndex - maxLen)..<endIndex])
}

// Example usage
print(longestCommonSubstring("abcde", "abfce")) // Output: abc

function longestCommonSubstring(s1: string, s2: string): string {
  const m = s1.length;
  const n = s2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  let maxLen = 0;
  let endIndex = 0;

  for (let i = 1; i <= m; i++) {
    for (let 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];
          endIndex = i;
        }
      }
    }
  }

  return s1.slice(endIndex - maxLen, endIndex);
}

// Example usage
console.log(longestCommonSubstring("abcde", "abfce")); // Output: abc

Time complexity

Space complexity

O(m * n)

The algorithm uses a 2D dp array of size (m+1) x (n+1) to store intermediate results, leading to O(m * n) space usage. Space can be optimized to O(n) using two rolling rows, but the standard approach uses full table.