Daniel Carvallo
2 min readSep 28, 2021

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

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

Daniel Carvallo
Daniel Carvallo

Written by Daniel Carvallo

My primary goal of doing this is the intellectual curiosity, the seduction of adventure.

No responses yet

Write a response