Algorithms_with_Shayan's blog

Longest Common Subsequence (LCS) in DP Playlist
By Algorithms_with_Shayan, history, 4 months ago, In English

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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 months ago, # |
← Rev. 2   Vote: I like it +88 Vote: I do not like it

Just a friendly suggestion: YouTube is filled with these standard questions. It would be very beneficial if you could create videos on some advanced topics or challenging problems (old ICPC or IOI or IMO problems ).

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    You are right. As I mentioned earlier I'm trying to cover both beginner and advanced content,

    Thanks a lot for your suggestion. I will start solving old ICPC, IOI, and IMO problems.

    → Reply
»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

actually the quality of the videos is better than any video keep up the goodwork the community needs people like you

→ Reply
»
4 months ago, # |
  Vote: I like it -7 Vote: I do not like it

You are doing a great job. Keep it up.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can you share some problems related to LCS please :)

→ Reply
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Really nice video, and thank you for the clear explanations without skipping over the little details.

In the future, could you please also add 2-3 similar problems to the one you're discussing? Additionally, I would love to see a video where you discuss the topics you consider a must-study for improvement. It would be great if you could rank them based on relevance and share some resources you liked for certain topics.

→ Reply