Longest Common Substring | Practice Medium 0 attempts
GeeksforGeeks ↗

Longest Common Substring | Practice

Medium Dynamic ProgrammingMemoization GeeksforGeeks

Given two strings s1 and s2, find the length of the longest common substring. A substring is a contiguous sequence of characters within a string, unlike a subsequence which need not be contiguous.

Example 1:

Input: s1 = "ABCDGH", s2 = "ACDGHR"
Output: 4 (substring "CDGH")

Example 2:

Input: s1 = "ABC", s2 = "ACB"
Output: 1
Sample Input
—
Sample Output
—
Constraints
  • 1 <= |S1|, |S2| <= 500
Test Cases
Case 1
Args: ["ABCDGH","ACDGHR"] Expected: 4
Topics
Dynamic ProgrammingMemoization

Approach: Dynamic Programming

Create a 2D DP table where dp[i][j] stores the length of the longest common suffix ending at s1[i-1] and s2[j-1]. If characters match, dp[i][j] = dp[i-1][j-1] + 1. Track the maximum value seen.

function longestCommonSubstring(s1, s2) {
  const m = s1.length, n = s2.length;
  let max = 0;
  const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(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;
        max = Math.max(max, dp[i][j]);
      }
  return max;
}

Time Complexity: O(m × n)

Space Complexity: O(m × n)

Saved in this browser only. Private to you.

JavaScript