Hey guys,
I have prepared a video discussing LCS and added it to my YouTube DP playlist.
The Longest Common Substring (LCS) is the length of the longest string shared between two given strings. It's like finding the common set of characters that appear in the same order in both strings.
A subsequence is a sequence of characters that appears in the same order as they do in the original string but not necessarily consecutively. In contrast, a substring is a contiguous sequence of characters within a string.
Here is a code for LCS:
int lcs(string X, string Y) {
int m = X.length();
int n = Y.length();
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X[i - 1] == Y[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
Link of the DP playlist:
https://www.youtube.com/playlist?list=PLzDmwrrgE-UVKGwxoYao36BVTvBozwLoG
Feel free to join our Discord channel to further discuss these topics and chat with the CP legends I will interview.
As always, please let me know your feedback and suggestions.