Longest Common Substring | Practice Medium 0 attempts
GeeksforGeeks ↗

Longest Common Substring | Practice

Medium Dynamic ProgrammingMemoization GeeksforGeeks

Given two strings s1 and s2, determine how long the longest substring they both contain is. Remember that a substring must be made of consecutive characters pulled straight from the string — unlike a subsequence, you can't skip characters along the way.

Input Format
Implement longestCommonSubstring(s1, s2). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
s1 = "ABCDGH"
s2 = "ACDGHR"
Output
4

Example 2

Input
s1 = "ABC"
s2 = "ACB"
Output
1
Constraints
  • 1 <= |S1|, |S2| <= 500
Test Cases (2)
Case 1
Args: ["ABCDGH","ACDGHR"] Expected: 4
Case 2
Args: ["ABC","ACB"] Expected: 1
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.

javascript
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