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.

You can watch the video here.

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.

https://discord.gg/fYj9xMam7f

As always, please let me know your feedback and suggestions.