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 1

• Bottom-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)