23 Printing Longest common subsequence
ฝัง
- เผยแพร่เมื่อ 12 ก.ย. 2024
- Printing Longest Common Subsequence
Given two sequences, print the longest subsequence present in both of them.
Example:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
PROBLEM STATEMENT LINK:www.geeksforge....
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
![โฮ่ง! (SUGOI) - LYKN [ OFFICIAL MV ]](http://i.ytimg.com/vi/nFp4zjAARFs/mqdefault.jpg)
It seems so long video, but same video is repeating again... watch till 26:47
he should pin this comment.
I anyone sees this message , just like it to the maximum extent so that the comment gets some importance.
Thank you so much man. This scared me in the starting thinking that printing LCS is so tough considering the duration of the video
Thanks @surinder kumar I used to skip this video for last 2 months because of its length.
@@KANHAIYAKUMAR-qi7gx lol😅. Me too
Modi Ji after meeting Aditya in Real Life :-
Yeh DP wala hai kya ?????..
😂😂😂😂😂😂😂😂😂
😂😂😂
Sahi he. 😂😂😂😂😂😂😂😂😂
And after seeing these videos we say wah Aditya Bhai wah. , wah Aditya Bhai wah.
And other Yotubers bole to bole kya Kare to Kare kya, wah Aditya Bhai wah.
😂😂😂😂😂😂😂😂😂
Hahaha epic, also I gave u the 100th like 😁
Aditya sir u r amazing
Need a playlist of GRAPHS !!
yes 💯 please sir 🙏
@@ayushvats1808 did you find any?
yes please
@@sarthakarora6496 i found One Ridhi dutta.... like its good...but if you get any better do tell
@@nishantsah6981 striver and codebix
23 of 50 (46%) done! Nice explanation of printing -- yes, there is a repetition of concept, but the second half explains it in more details, especially how we traverse up the t matrix (IMHO) to get the common chars.
nice bhay
@@ultimatecreed5144 *bhai
Aditya Verma: Interesting tha na!!!!! :)
Inner me: Yeah!!!!! Veryyyyyyy Interesting :D
😅😅 Glad to know that 😅😅
@@TheAdityaVerma this question is not complete right.
Looks like for printing LCS, we can always use only the last row in the table.
i = m-1;
for (int j=0; j < n; j++)
if (t[i][j] != t[i][j+1])
cout
That's a very good observation bro
Yeah, Bro your solution is absolutely correct. I used your method to find the longest sub-sequence string in leetcode problem "Longest Common Subsequence" , and then returned the length of the string to verify, and solution was accepted. Basically I just used the code of "Longest Common Sub-Sequence" and just utilised the last row for my answer.
int dp[1002][1002];
class Solution {
public:
int longestCommonSubsequence(string s1, string s2) {
int i, j, n=s1.length(), m=s2.length();
string s;
for(i=0;i
www.hackerrank.com/challenges/dynamic-programming-classics-the-longest-common-subsequence/problem
wa in test2,3
why this doesn't work if we consider the last column consider the example shown in video itself at 16:39
what happen if multiple lcs exist then you approach the problem ??
Best DP playlist on youtube!! You have really contributed to learning of students who struggle with Dynamic Programming. I too had observed similarities in DP questions, but as I am a beginner, I did not have enough experience to relate stuffs. You have made someone's life easier. Keep going, looking forward to more videos!!
Actually, this video ends at 26:51, by mistake it repeats 3 times and becomes 1:20:55
thank for this info
Thanks bro 👊
my freinds used to say dp is tough in those days when i am beginner , now because of your playlist sir . i felt dp was not tough when we have teachers like you sir. in my 12th i used to link maths concepts so i dont need to remember new concepts, now you told us the dp in the same way which made the work easy 💌..thank you sir..
Bro make a playlists for greedy Algorithms !!
Yess atleast 15 questions
Yes
Yes
Yes
did I just watch this solution 3 times? I got scared when I saw video length at first. 27 minutes makes sense given how you describe.
I got scared seeing the length of the video as 1 hr 20 mins.
same dude, I left it for 2 days, thinking it was too big :(
@@lordbaggot same thing happend here too
@@lordbaggot same here 😂😂
@@indranilthakur3605 same .....haha
a good optimisation in this solution might be to just iterate till following condition is true while constructing the answer in reverse order
while(dp[i][j] > 0) instead of going till i or j is 0
yes I already got that, Thanks for confirmation.
I don't think i've seen better explanations, when it comes to dynamic programming. Sir, you are a life saver!
Awesome videos. Ground concepts explained so vividly. Will be glad if videos on graphs are made.
Ur channel is best channel for placements preparation
Thanks, do share if you like the content and help this channel grow. And yeah subscribe too 😅😅
@@TheAdityaVerma bro please help in solving one LCS typical problem give your WhatsApp number I will keep the question
placement hua ?
I was really scared with the lenght, mentally preparing myself thanks for the comments guys. and thanks aditya pls pls pls do graph theory and greedy, 1 month hai placement me and I wnt a job really badlyy
for graph you can prefer Tech Dose TH-cam Channel. He is too good.
Brilliantly explained. I am finding this channel very helpful. Thanks Bro and All The Best for future. Also, this video has one video running 3 times. Fix it, if posiible.
IK, but unfortunately it cant be fixed now 😕
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
@@TheAdityaVerma Waiting for "May", Thanks Brother! Great Explanation!❤️
@@TheAdityaVerma can you say which topic you are going to discuss ,
can you say date in May
So that we can schedule that topic in may
Was first afraid after noticing the length of the video but after I started I understood the concept in 15 min 😂 you are the best teacher
I was not getting even single concept of DP from other channels, but after watching your videos on DP I am doing it daily with great interest. Also looking forward for videos on Graph Data structure.
One of the best tutorials on TH-cam for DP. God bless you.
Please add playlist on Greedy algorithm, backtracking and Graphs if possible.
Thx a ton
Hey can u help me regarding backtracking greedy any yt channel?
Problem link for practice www.hackerrank.com/challenges/dynamic-programming-classics-the-longest-common-subsequence/problem
// Instead of adding 1 to the result we add the common
// character to the end of the value we already have
// else we just take whatever option has the longer string
string longestCommonSubsequence(string s1, string s2) {
int m = s1.size();
int n = s2.size();
string dp[m+1][n+1];
for(int i=0;i
This is a much more intuitive method
You can get the chars without using dp for n^2 complexity by just taking a string and appending at the end if true for the if condition.
Moreover, a better approach would be to adding two lists and taking complement.
bro,
can you provide the link gfg ,leetcode
how to get all the lcs ?
i used another approach and it worked fine :-
1)make dp of strings.
2)initialize with empty strings instead of 0.
3)when i-1==j-1 ,do dp[i][j]=dp[i-1][j-1]+string1[i-1]
else
do
if(dp[i][j-1].size()>dp[i-1][j].size() )
dp[i][j]=dp[i][j-1]
else
dp[i][[j]=dp[i-1][j]
4)woah! done just return dp[n1][n2];
Really thanks bhai I was also thinking the same but couldn't able to write the code correctly u helped me thanks
You can just add the strings directly to the table instead of length:
def lcSubString(text1, text2):
m = len(text1)
n = len(text2)
t = [["" for i in range(0, n+1)]
for i in range(0, m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
t[i][j] = t[i-1][j-1] + text1[i-1]
else:
if len(t[i-1][j]) > len(t[i][j-1]):
t[i][j] = t[i-1][j]
else:
t[i][j] = t[i][j-1]
return t[m][n]
we can directly store the strings in the matrix, we can initialise the 0th row and column with an empty string and when s1[i-1] == s2[j-1] we can do this - t[i][j] = s1[i-1] + t[i-1][j-1] else
if(t[i-1][j].length() > t[i][j-1].length()){
t[i][j] = t[i-1][j];
}else{
t[i][j] = t[i][j-1];
}
and print reverse of t[m][n] in the end
Been watching your videos since past 3-4 days and I'm sure I'm understanding each and every bit of it. Thanks a lot 😊
JUST WANTED TO SAY - "THIS DP PLAYLIST IS A GEM", i recommend everyone to watch who faces difficulties in DP problems.
and I also Wanted to say a Big Thank you to Aditya Verma bhaiya for making this playlist and uploaded on youtube as free for everyone.
Thanks for dp series.
For printing lcs, we can just take last row of dp table, and jaha jaha integer first time occurr hora hai, vo index string2 me se print karado, answer mil jaega.
are you sure that it will work?
Ya I also think so.
This is good too.
It wont work in all the cases
Eg: "MZJAWXU" & "XMJYAUZ"
Expected output : "MJAU"
Output using this method: "MZAU"
The way you taught in all previous videos , it didn't take me anytime to think of the solution and I could write the code in one go. But I watched this whole video to make sure I am not missing anything.
DP requires so much effort to understand but once understood you will be the person with much powerful brain.
Hi All,
To print the "Longest Common SUBSTRING" between the 2 strings please see below solution (Like if my approach worked for you) -->
//First step should be to create the t[i][j] array containing the length of the Longest Common Substring.
Please dry run the code once for String A = "ABCDFH" and B = "ACDGHF" and then you'll understand why I've added while inside while and j==0 conditions (basically tried to cover all the edge cases)
StringBuilder res = new StringBuilder();
int i=n,j=m;
while(i>0 && j>0){
if(str1.charAt(i-1) == str2.charAt(j-1)){
if(dp[i][j] > 1 && dp[i][j] > res.length()){
/*Since it may be possible that we've already stored a smaller length string in the result string so we just set it's length to zero and then keep on adding it in the result string till the length doesn't becomes zero*/
res.setLength(0);
while(dp[i][j] > 0){
res.append(str1.charAt(i-1));
i--;
j--;
}
}
else{
/*Now if the two strings just contains a subsequence then simply store the first matching character of it into the result string if it's not empty otherwise ignore it and MOVE ON!!
if(res.isEmpty()){
res.append(str1.charAt(i-1));
}
j--;
if(j==0){
i--;
j=m;
}
}
}
else{
/*Basically we're just making sure if dp[i][j] is 0 or not(which it will be definitely) so we simply decrease the column(j) but before proceeding we need to make sure that if j has reached zero so we decrease the value of i and reset the j to m (It's basically opposite to the for loop condition of j=0; j
This is exactly what I was looking for. I had spent hours on this problem before finally giving up since printing Substring is way more trickier than Subsequence because we can have multiple Substrings as well in the output. Your code is working for me.
You can also use this logic the print lcs, that too i n correct order lol. took me a while to think it out
string s;
if(t[n][1]==1) s.push_back(text2[0]);
for(int i=2;i
You are god's gift to those who don't want to go/pay for coding institutes 🤠
Thanks for making this legendary dp playlist 😎♥️🎯
segment tree and two pointer technique par video bnao......please
aur aapki series superb hai ...it's really amazing
Great going Aditya. I was always afraid of DP but you made it look so simple. I really needed someone to explain it from the start and found your playlist. Hats off to your teaching skills :)
We can also return longest common subsequence directly from the function. The tested code using memoization is as shown
#include
string t[1001][1001];
string longestsub(string s1,string s2,int n,int m){
if (n == 0 || m == 0)
return t[n][m] = "";
if (t[n][m] != "-1")
return t[n][m];
if (s1[n-1] == s2[m-1]){
string lcs = longestsub(s1,s2,n-1,m-1);
lcs.push_back(s1[n-1]);
return t[n][m] = lcs;
}
else if (s1[n-1] != s2[m-1]){
string l1 = longestsub(s1,s2,n-1,m);
string l2 = longestsub(s1,s2,n,m-1);
if (l1.length() >= l2.length())
return t[n][m] = l1;
else if (l1.length() < l2.length())
return t[n][m] = l2;
}
}
string findLCS(int n, int m,string &s1, string &s2){
// Write your code here.
for (int i = 0; i < 1001; i++) {
for (int j = 0; j < 1001; j++) {
t[i][j] = "-1";
}
}
string ans=longestsub(s1,s2,n,m);
return ans;
}
Thank you man
Aditya , Your are SuperMan of the coding community..Please upload some more videos as we are having more freee time these days to learn and grasp new concept...Thanks
Best videos on dynamic programming so far.Please make videos on trees/graphs questions or important questions from leetcode and other coding platforms.
public class printLCS {
public static void main(String[] args) {
String s1 = "abdefjs";
String s2 = "xadfsx";
int n = s1.length();
int m = s2.length();
// Create a 2D DP (Dynamic Programming) table with dimensions (n+1) x (m+1)
int[][] dp = new int[n + 1][m + 1];
// Initialize the DP table with zeros
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < m + 1; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0; // Base case: If either string is empty, LCS is 0.
}
}
// Fill in the DP table using a top-down approach
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// If the current characters match, add 1 to the previous LCS length.
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// If the current characters do not match, take the maximum of the LCS
// when one character from either string is excluded.
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int i = n;
int j = m;
String s = "";
// Backtrack to construct the LCS string
while (i > 0 && j > 0) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
s += s1.charAt(i - 1);
i--;
j--;
} else {
if (dp[i - 1][j] > dp[i][j - 1])
i--;
else
j--;
}
}
// Reverse the LCS string to get the correct order
String ans = "";
for (char ch : s.toCharArray()) {
ans = ch + ans;
}
// Print the Longest Common Subsequence
System.out.println(ans);
}
}
u are really a great mentor....plz make playlist on graph too...
After seeing the length of this video my instincts said to me there might be a possibility of wrong editing... And it turned out true.. Lol. Great content sir, thank you 🙏❤
Brother in general out of 10 hindi words I can understand only 2
But in your teaching concepts taught me language
What type of legend you are bhai❤️
Keep going ur explanation
This channel is like the best channel for placement preparation, i have learnt so many concepts from this channel, which they never taught in college. Keep up this work and continue making more videos. These videos are really helpful. Thank you so much for these preparation skills.
Nice Video Bhai. Just a minor suggestion which wont make much of a difference but the reverse part for getting the LCS isn't required. If we know the length of the sequence, we can just create a char array of length = lcs and start from the rightmost end/index of the char array and copy the characters which match accordingly. You are doing a wonderful job Bhai :) Cheers.
You can still make it better by writing in this way ans = a[i-1] + ans; where ans is the string to be returned.
@@kumarivandana1554 not as optimized because appending in the front takes O(n)
If you do not want to traverse at the end, this is also a possible implementation:
string printLongestCommonSubsequence(string text1, string text2) {
int m = text1.length();
int n = text2.length();
vector t(m+1, vector(n+1,""));
for(int i=1; i
We might not need to traverse the dp array again, as while matching the characters we can add the common characters in the string variable that we can create before the iteration.
void printLCS(string &a, string &b, int n, int m)
{
vector dp(n+1, vector(m+1));
for(int i=0; i
i think we need to start from backtrack only because if the character is present multiple times in string then it will add it again to ans which we dont want unless it is present in both
This problem can be solved in another method just like original LCS problem. Initialize first row and column with empty strings. As we iterate if match happens we keep adding the character and store the string itself in t matrix. last element will be the answer. For length we can just measure length of the final string. We can even print all possible subsequences easily by this approach. And we don't have to do anything after filling the t matrix.
thanks again for your dedication
I have a query ....
while iterating backward Table and if the character at that position is not equal we have to choose the max of [(i-1 , j) , (i ,j-1)] and then we go to that position....
what if both the values are Equal???
we can take a relevant example ---> X= " abxyzc" , Y=" abkkkc"
0 0 0 0 0 0 0
0 1 1 1 1 1 1
0 1 2 2 2 2 2
0 1 2 2 2 2 2
0 1 2 2 2 2 2
0 1 2 2 2 2 2
0 1 2 2 2 2 3
Here is your dp matrix, and answer is correct which is abc
@@AnikashChakraborty thanks for your answer
But my question was different...which has already cleared
@@mokshmalhotra7032 I think I got the question and from the dp matrix you can see than after 3 you go to the upper left element and then keep on traversing till left or up (depends which condition is former) and then traverses till up or left(whichever condition is later) till it finds an equal element. Cool!
@@AnikashChakraborty ya...right
I was confused at the first time...but then i tried to go in one direction and got the answer
Btw ..thanks for reply ^_^
We can just make use of the earlier concept and change the dp array datatype to String and append the longest subsequence .Below is my code :-
class Solution {
public String longestCommonSubsequence(String text1, String text2) {
int n=text1.length();
int m=text2.length();
String dp[][]=new String[n+1][m+1];
for(int i=0;i
great technique...👍
please dont stop making videos!! this playlist is genius!
This video is repeating trice. Don't be scared of it. Watch till 26:47
Can't we do this push operation when making the dp? in the if condition?
I was thinking the same thing. Like that is very obvious, but is it correct?
Here is the code for it
string lcs_tabulation(string x, string y, int n, int m, std::vector &dp){
rep(i,0,n+1){
rep(j,0,m+1){
if(i==0 || j==0){
dp[i][j] = "";
}
}
}
rep(i,1,n+1){
rep(j,1,m+1){
if(x[i-1] == y[j-1]){
dp[i][j] = (dp[i-1][j-1] + x[i-1]);
}
else{
dp[i][j] = ( sz(dp[i-1][j])>sz(dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1]);
}
}
}
return dp[n][m];
}
@@pranaypb8158 did this worked on geeks for geeks problem link
@@mickyman753 do you have print lcs print problem link?
@@shreyasaxena5169 problem link will be always in the video's description ,th-cam.com/users/redirect?event=video_description&redir_token=QUFFLUhqa0l0SGNFMVUxaTd4dFF6LXVzUk1TZ0dESThJZ3xBQ3Jtc0tseWtjMkttUG1EX216dlNYTDk1SDdQZ1V6UHJBM0dRbWJtaFoyRUV4ZVFSek1BYldZWDh1VS1MUExyNm5LWEYzNkY5NjdNM01wOFJKczdtWkdlc1ZpRGNMdnZmdkJEX0libDRuUzBKTTZOWHJpZHoyaw&q=https%3A%2F%2Fwww.geeksforgeeks.org%2Fprinting-longest-common-subsequence%2F
I was just scared because of the length of the video, the Way explains is incredible 👍 ❤ lots of Love from ITER,BBSR
I had a doubt, during the creation of table " t ", we do check for characters to be similar ( with this code : if a[i-1] == b[j-1] and then we do necessary increments for the LCS count ), then we can actually push the characters to a string at that very moment right ? Like instead of performing what Aditya just said in the above video.
EDIT : My method was wrong, I dry run the code and checked, we will get multiple chars as well so the above approach is the right one .
I had same doubt thanks for editing and clearing it out
Same Doubt, Can u please Explain why there is Repetition of characters
@@siddhant_yadav check for example: str1="abx", str2="xab", the main point is as we have to find the max length subsequence there can be multiple occurrences where str1.charAt(i-1)==str2.charAt(j-1) but that character does not contribute in the max length subsequence.
but it says longest common subsequence, not substring
We can do this in this following way too. Just a small change from original question. No need to create a dp array of int.
vector dp(n+1, vector (m+1, ""));
for(int i=1; i
Did u use memoization? Because of initialising full table with " "
Aditya Verma Sir aapne ne mere aur sayad jo bhi bachhe iss video ko dekhenge unn sab ka DP ka daarrr bhaga diya bohot sukriyaa...
best playlist I have followed till date!
You can also think of this approach like a Depth First Search and we choose "adjacents" based on the choices we previously made in the past to build the 2D array.
sir, you have explained the concept very well.
but suppose we are given the strings as,
s1= BQPQBPQ
s2 = QPPBQ
then there will be two longest common subsequences possible.
first is QPBQ
second is QPPQ
(both are valid )
how can we get both the strings as an output?
Before watching your videos* Dp is out of my syllabus.
After watching your video* I can teach dp now 😅
really helpful brother!.also can you please tell me how to print longest common substring.?...and one more thing to this is that if multiple answers exist then choose the one with smaller starting index.
thanks!.
Instead of reversing we can initialise the string sol = " " initially and when they are equal then update sol to CharAt(" str1") + sol and return sol at the end
or simply store in stack and print the stack
will this work fine?
@@motormaza_riders ??
Bhai bht hi jabardast padhate ho aap ek ek concept clear ho gai thanku so much it really helped it
I understand the whole approach but it can be very simply solved when using the original code, basically wherever we are calling t[i][j] = 1 + t[i-1][j-1] just add print(x[i-1]) and you get the simple output as reverse of longest common subsequence order which you can reverse in multiple wayss ??
Correct me if I am wrong
best dp course on the internet
Bhai dil se sukriya padhaane k liye. ❤
javascript code :-
let string = "abcdef"
let string1 = "abuiopmnbv"
let n = string.length
let m = string1.length
function lcs(st,st1,n,m) {
let dp = new Array(n+1)
for(let i =0; i
Awesome content now I understand how to proceed with such questions
One more question what will be the code variation if it had been printing substring
Better approach is storing string itself in dp of string,
string c[n+1][m+1]; initialize with blank for n==m==0
then just do
if( t1 [ i - 1 ] == t2 [ j - 1 ])
{
c[ i ][ j ] = c[ i - 1] [ j - 1 ] + t1[ i - 1 ];
}
else
{
c[ i ] [ j ] = c[ i - 1 ] [ j ].length() > c[ i ] [ j - 1 ].length()
? c [ i - 1 ][ j ] : c[ i ] [ j - 1 ];
}
cout
Thank you so much!!
Best video on youtube for DP!!
The way you are teaching I think u will become the number one teacher. You teaching style is like koi apna banda baju me beth ke padha rha ho....
Best DP course on internet!
@Aditya verma can't we add matching characters in a string array at the same time while filling a 2d array under the first condition where elements from both string array matches?Why do we need to write separate code for it.🤔🤔
can't we just add this line
if(text1[i-1]==text2[j-1]){
t[i][j]=1+t[i-1][j-1];
cout
now kind of feeling some confident in DP. thnx to u bro... Brilliant efforts..
In the previous videos and also this one, to get t[i][j] we only use the previous row and all columns of the previous row, so can we not just use a 2D matrix of size t[ 2 ][ n ]??
This I think would apply to the other KnapSack problem variations also and it makes the space complexity linear from O( n^m )
What would you suggest?
can't we just add this line
if(text1[i-1]==text2[j-1]){
t[i][j]=1+t[i-1][j-1];
cout
Won't work. We are interested in only that match which contributes to max matched length or LCS till that point.
U might end up adding the same character many times.
javascript code :-
but you have to just reverse it
let string = "abcdef"
let string1 = "abuiopmnbvc"
let n = string.length
let m = string1.length
function lcs(st,st1,n,m) {
let dp = new Array(n+1)
for(let i =0; i
others dp tough hai, dp yeh, dp woh
aditya: hold my t
Great video !! May I know how I can become as efficient as u & since how long have u been coding.....hope I get a reply
would really like a playlist on graphs but its fine whenever you get time please make one thankyou
i have a doubt ,the lcs matrix we create is of size (m+1)*(n+1) whereas while traversing that matrix we are writing a[i-1]and a[j-1] with i=m and n=j so it wont chec k the values at (m,n)
correct bro i=m+1,j=n+1
just curious, what if t [ i - 1 ] [ j ] == t [ i ][ j - 1] ? which value will we take ? and why ?
thank you in advance :)
Yes actually that's true. It's strange that nobody mentioned this. I was thinking about this the whole time while watching this video. Actually for this we can either perform recursion from [m][n] to when either m == 0 or n == 0. When t[i-1][j] == t[i][j-1] we perform 2 recursive calls, one for each indices (i-1, j) and (i, j-1) and form the output subsequences according. Also, in an iterative manner we can use a deque which stores i, j indices. Whenever we face t[i-1][j] == t[i][j-1], we push both indexes (i-1, j) and (i, j-1), one at the front and one at the back so as to not break the chain of subsequence lettering.
Awesome explanation by Aditya.
Can't we keep collecting the equal string while traversing from t[0][0] to end?
I used the same...it is working..add initialize s = "" outside the loop and s = s + p(i-1).toString; add this when string matches
Will take O(n^2) here much less complexity
@@AnilKumarBairy I guess this won't work if we have multiple matching subsequence
Nice explanations boss @Aditya Verma..
one thing in above question.. instead of having a separate while loop and then storing it in a string.. can't we store it while forming LCS matrix only when the equality condition arrives ??
Can we start from (0,0) and end at (m,n) so that there is no need to reverse the string ?
or you can just add the characters in front of the string rather than back
Just loved your videos on DP ♥ but will there be any videos coming on graphs? 🥲
The video is till 26:00 only, man the thumbnail should change for a guy who is developing the habit of sitting down to study, this video length could be really scary and easily delay continuity. So much relief now. ohhh!!!!!! n one could easily learn something from this i.e. everything's a mind-set think of it as small everything changes and think of it as big, whoosh! power to accomplish decreases. LOL. So make the big small and go on!!. Btw thank you for the videos it helps a lot.
Seriously aditya bhaiya please reduce the length of video, I love your videos I m following your DP series and I am feeling proud to say that I have understood alot and before you I watched video of ALL TH-camRS like CodeNcode, Abdul Bari, TakeUforward But When I understood the problem then after several weeks I just forgot the Solution, But You describe in such a way that we don't required to read this again THANK YOU, YOU ARE THE ONE OF THE BEST CREATURES OF GOD.
But there is only One problem in video which is You are repeating so much and increase the length of video, Buddy please correct this
Thanks brother, btw this video got repeated 3 times (editing error), just watch the first 30 minutes or so.
@@TheAdityaVerma thanks a lot bhaiya, for ur existence... : )
we can use s.insert(s.begin(),a[i]) =>>>in case we use s as vector of characters.....
and s = a[i] + s =>>> in case we use s as string.....
Both will directly give reversed or accurate string or vector of chars in result....
Hey @Aditya Verma thanks for this explanation but we missed one case here
Suppose a[ i-1 ] != b[ j - 1 ]
and if ( t[ i ][ j-1 ] == t[ i-1 ][ j ] )
what next operation shall we perform? This case can come if you have more than 1 LCS
apply dp again to traverse all the paths. a hard gfg problem is based on this concept only.
@@pratikdas1780 How to do this can you please elaborate ?
We can also just append equal characters to a string while doing LCS , no need of the extra calculation in the end .
I'm a fan tho
at first glance seeing the time stamp as 1:20 made me feel scared that what the sir is going to teach in this much time but after 26:57. me be like : aapke sath ek chota sa prank hua hai!!
camera me dekh k ek baar hath hila do
🤣🤣
@@TheAdityaVerma Sir please make playlist on graphs and greedy.
Bro why creating table at once and printing string again during storing values into memory itself we can print our string
if(a[i-1]==B[j-1]
(cout
How to print the LCS using recursion? I am struggling to figure it out.
what if t[i][j-1]==t[i-1][j]?? now where to move
Did you figure it out?
I have the same doubt too. Please help if you know
@@dontknow592 if( t[i][j-1]>t[i-1][j]) j--; else i--; in the else part we are considering if( t[i][j-1]
@@PRIYANKAKUMARI-iz2no Thank You. Got it 👍🏻
Love YOu Bro , Really Your Video is God Level
Its such a important topic ki bhai ne video me 2 bar revise kara diya hai ...amazing and simple to understand without any doubts
By just adding 1 line (define a string s and then write s = s + x[i-1] ) below choice diagram code)in code of longest common sub sequence , we can achieve the answer. Is there any problem i may face in this solution ?
Here is my full code::->
x=input()
y=input()
n=len(x)
m=len(y)
t=[[-1 for x in range(m+1)] for y in range(n+1)]
for i in range(n+1):
for j in range(m+1):
if(i==0 or j==0):
t[i][j]=0
s=""
for i in range(1,n+1):
for j in range(1,m+1):
if(x[i-1]==y[j-1]):
s=s+(x[i-1])
t[i][j]=1+t[i-1][j-1]
else:
t[i][j]=max(t[i-1][j],t[i][j-1])
print(t[n][m])
print(s)
This is assuming that there is only one longest subsequence. For example x="abcba" and y="ababc" has 2 longest subsequences: "abca" and "abab". The approach discussed here will return only one of these as the answer
Bhai 1.20 dekh ke dar gaye the ki kya Hoga print LCS me .. 😂
Thanks for making these videos and all the best for flipkart.