Longest Repeating Subsequence | Dynamic Programming | LCS
Вставка
- Опубліковано 5 жов 2024
- This video explains a very important dynamic programming interview problem which is to find the longest repeating subsequence length as well as string.This problem is a variation of the longest common subsequence. I have first explained the problem statement and then I have shown how this problem is similar to Longest Common Subsequence.I have used simple examples and have also shown the dry run for finding both LRS and LRS string.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
USEFUL VIDEOS:-
Longest Common Subsequence: • Longest common subsequ...
Longest Common Substring: • Longest common substri...
Uncrossed Lines: • Uncrossed Lines | Dyna...
#dp #lcs #lrs
Just amazing. I so much like them that even after 2 FANG offers I am glued to these. Again all thanks to you for coding Qs. Kudos to also the fact while people are busy making paid sites, you are making this high quality content free to all aspirants via UA-cam.
Thanks for supporting :)
Please ping me on LinkedIn
Crystal clear explanation, the first channel i prefer after seeing the problem statement. keep making videos
Thanks
in else if condition: not s[i][j] its s[i-1][j-1];
if we consider loop i=0 &j=0 then dp[0][j] &dp[i][0] not valid or if we consider loop i=1& j=1 then we miss 0th charecter of string.
Came here after watching Aditya Verma's video ... best explanation!
Sir, at 6:03, the string AXXX, why didn't you also consider x(3) -string-1 combined with x(1), string-2, they both x at 3rd index of string 1 and x at 1th index of string-2 are not overlapping by indexes.
I have same doubt
I guess it may not overlap
To have all 3 x's the indexes would have to match so you can only do 2.
It should be s1[i-1] == s2[j-1] in else if condition of the code which you have explained.
That will be correct if he had added 1 to the length of row and col of the table
Can we return the string value of LCS in same way as you did in the last part of the video ?
14:10 ==>> This is the tablular form where LCS of the 2 strings at a given index(2d) are not at the same index in original string
The explanation is so clean❤️
Thanks :)
Nice video request you to please advise which software you using for display
Wow Really Nice Explanations !!
Thanks :)
Awesome video!
Thanks
Your videos are awesome! Keep producing these amazing videos.
Thank you. Yea I will.
Nice explanation
Thanks :)
I dont understand the example of 'AXXX' .here the longest repeating subsequence is XX but no matter which index of X you take when repeating 'XX' one index will be common...please explain
look at the constraint,corresponding characters should have different indices in the main string
Thank you my doubt got cleared ..@@bharathkumar5870
you are great sir!
amazing vedio
Thanks
Initialization Condition is done according to LCS/LRS logic ?... i.e., filling 1st row & 1st column of DP Table?
yes
A higher time complex approach
Cleanest❤
How to declare lsc[][] 2d array in when we are returning string ? (I.e in second case )
Did you try vector of vector of string ?
what about aaa, isisi
can we use the same method for forming lcs as you shown in this video
Yea
Hi Tech Dose, is this a leetcode problem?
I din't find it on leetcode.
Uncrossed Lines
I EXPECT A REPLY ON THIS
length is coming wrong in one of mine testcases ,n=157 expected =45,output=44
gjlapopkvxfgvicetcmkbljopgtqvvhbgsdvivhesnkqxmwrqidrvmhlubbryktheyentmrobdeyqcrgluaiihveixwjjrqopubjguxhxdipfzwswybgfylqvjzharvrlyauuzdrcnjkphclffrkeecbpdipu
Hard to check this for me
Please at least do a code walkthrough in the end🙏
This was LCS so dint do it.