Longest Common Substring/Subsequence [DP Problems]

Photo by Braňo on Unsplash

The longest common substring and longest common subsequence problems can be solved with a similar algorithm, for the first one we must find a max value in a grid and for the second one, we should check the last cell in a grid.

Why is a grid used? Well, it is because the Dynamic Programming (DP) technique is used which generally involves breaking a problem down into smaller parts, where these parts are the grid cells. The grid is built with two strings, an array of characters or numbers, one mapped on the x-axis and the other on the y-axis.

Both problems can be solved with DP, they can be broken into discrete sub-problems where each of them can be mapped to the cells of a grid; important to say that each sub-problem doesn’t depend on each other.

The basic if-else statement for solving both problems looks like this:

if word1[i] == word2[j]:
  grid[i][j] = 1 + grid[row — 1][col — 1]
else:
  grid[i][j] = 0 // substring
  grid[i][j] = max(grid[i - 1][j], grid[i][j - 1]) // subsequence

And thanks to this little snippet, we can solve two problems with just one small change. The formula to me it’s like this: If the character from string 1 doesn’t match with the corresponding character from string 2, then the value for the current cell is zero. But, if they do match the value for that cell is the value of the top-left cell plus one. For the subsequence, if they don’t match then the value for the current cell is the larger/highest value.

718. Maximum Length of Repeated Subarray

Longest Common Substring

1143. Longest Common Subsequence

Longest Common Subsequence