In this article, we will learn to resolve the Longest Common Substring problem by using a dynamic programming algorithm

## Problem

Given two strings,

`S`

of length`m`

and`T`

of length`n`

Write an algorithm to find the longest substring of both

`S`

and`T`

## Example

Input: given two strings "ABABC" and "BABCA"

Expected output: "ABC"

## Approach: Bottom Up Dynamic Programming

Optimal substructure:

`L(i, j) = L(i-1, j-1) + 1`

if`S(i-1) == T(j-1)`

with`L(i, j)`

is the length of the common substring at character`S(i)`

and`T(j)`

For the above example, the longest common substring "ABC" has the length at the last common character

`C`

of both`S`

and`T`

,`L(5, 4)`

, equals to the length at the immediate preceding common character`B`

,`L(4, 3)`

, plus 1Bottom-up filling the 2D array

`L[m+1][n+1]`

and keep track the max length and start index of the longest common substring

```
public class String_LongestCommon {
static String longestCommonSubstring(String S, String T) {
int m = S.length();
int n = T.length();
int[][] lengths = new int[m+1][n+1];
int maxLength = 0;
int endIndex = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j== 0) {
lengths[i][j] = 0;
}
else if(S.charAt(i-1) == T.charAt(j-1)) {
lengths[i][j] = lengths[i-1][j-1] + 1;
maxLength = Math.max(maxLength, lengths[i][j]);
endIndex = i;
} else {
lengths[i][j] = 0;
}
}
}
return S.substring(endIndex - maxLength + 1, endIndex + 1);
}
public static void main(String[] args) {
System.out.println(longestCommonSubstring("ABABC", "BABCA"));
}
}
```

## Complexity

Time complexity: O(mn)

Space complexity: O(mn)