24 Shortest Common SuperSequence
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- Shortest Common SuperSequence
Given two strings str1 and str2, find the shortest string that has both str1 and str2 as subsequences.
Examples:
Input: str1 = "geek", str2 = "eke"
Output: "geeke"
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.
I can't believe we are getting all this for free! Pure Gold! Thanks a ton, bhaiya! :) :)
Welcome brother !! And yeah its for free, the only thing I would ask you is to share the channel with the needful to help others and to the help the channel grow.
@@TheAdityaVerma i done it 3000 times bhai
@@tarunreddy8243 Eh ooru mandi
@@pruthvirajk6019 me hyderabad
@@TheAdityaVerma Bhai I have shared in all of my college coding club Groups of every year. Keep Making More Videos.
@14:23 , I said to myself "LCS" and then after a cinematic pause you said "answer to bol hi diya hoga ab tak"
this kind of connection between student and a teacher is even rare in live 1 to 1 classes :)
thank you very much for such a wonderful playlist !!!
pinch
Han bhai
Same here
Not bragging but mereko toh prblm statement padhne se hi pata chal gya Aditya Sir OP
Same here
I just said "longest common subsequence" and you said " I hope Tumne abtak bol Diya hoga answer, itna Jo padhayaa Hain" 😂
Thanks wouldn't be enough a word to express how thankful I actually am for this tutorial! I'll always recommend this channel to everyone I know! Great work!🌻
Thanks Tiyasha 😅 I am glad that you answered that correctly !! And yeah thanks for the sunflower !! 😂😂
@@TheAdityaVerma 😂 You're welcome!
Exactly same bhai :')
@@adhishmalviya2408 Nhi milega Sunflower ke liye Thanks XD
@@TheAdityaVerma men will be men
teacher: so everybody open the book and head to page numb...
aditya: pehle bed tea do
[5:05 time stamp reference]
i can somehow imagine him asking for a bed tea from the school teacher
@@mickyman753 ab school ke bache se dp padhenge btech wale
@@yogeshyts arey whitehat Jr. ke ad main Chintu app bna rha hai , toh phir school ka baccha bhi dp kr hi lega
@@mickyman753 😂🔥
Btw which clg?
@@yogeshyts sgsits,indore , you?
Nicely expalined, the good part in your tutorial is that you cover all the basics also while teaching on a topic. Thanks For making excellent video series on Dynamic Programming. Keep it Up !!
Thanks for watching dude !! ✌️❤️
@@TheAdityaVerma please make a playlist on graphs also.
It's a pain in the ass to see such a high quality video get such less number of views. I hope this channel grows exponentially.
Ha bhai apna selection hne ke bad par😂
@@yuvrajoberoi7834 bhai yeh bol bol kar sabko scheme bata dega😹
@@raviashwin1157 bhai 25 din ke andr selection lelo😂
@@yuvrajoberoi7834 🤣
@@raviashwin1157 ashwin bhai aap cricket khelo yha kha aa gye 😂
Below is the detailed explanation for printing of supersequence. Here we first do lcs and then like @Aditya showed in printing of LCS you can check for following:
1. if character exists in both add to string.
2. if not check dp[i][j-1] >dp[i-1][j] which means the str which represents column its jth is not common so push that but dont push row as chances are it can still exist.
3. Do opposite in else.
4. once out of while loop check if i or j is greater and insert them into string.
Below is the code for that:
string lcs(string str1, string str2, int m , int n) {
int dp[m+1][n+1];
for(int i=0;i 0) {
s.push_back(str1[i-1]);
i--;
}
while(j > 0) {
s.push_back(str2[j-1]);
j--;
}
reverse(s.begin(), s.end());
return s;
}
Thanks
Beautiful code
Last loop while(i>0) is not clear. Can you please tell why is that done.
Perfect.. was just looking for it!! Thanks man😊❤
@@jaxsriv1052 It is basically for- if there is any character left unchecked for String1 then it copies it to our answer String,, Same goes for while(j>0).. if any character is left unchecked in String2, it simply adds it to our answer String. Hope that clarifies ur doubt!
Shit man! Are you serious?
Kya padha rahe ho yarr.. my first reaction after hearing that this is purely related to LCS => "Ohh My God.."
You are awesome yarr.. !! Jio bhai.. bahot saari duvaye..!!
24 of 50 (48%) done! @4:47 'teacher aaye to unhe kehdo ki muzhe bed tea chaahiye' :-) I was all serious trying to follow-along the logic and your dry humour in the middle of it cracked me up!
same
This playlist is making me fall in love with DP.
nice explanation.
I concluded that its basically n(AUB)=n(A)+n(B)-n(A ∩ B)
sorry man but its not the case
take for example :
string 1="hxmngqmf"
string 2="gnapcnty"
by your method you will get 14
but the answer is 15.
But it is for sets not for strings because.. A String can contain duplicate letter
@@priyarani9569 exactly
@@priyarani9569 Also not necessarily A intersection B contains the common letters in the same order. That's also a reason.
puluthi
14:25 Twist of the century! :jaw_dropping:
I improved understanding of Hindi and DP after watching these :)
Aditya verma, you are gold man. I have been daily watching your DP series and I have learnt a lot. Thank you. And I have one more request, apart from DP, graph problem is another thing people find difficulty in finding patters. After DP series, I will be looking at your other series too. But graph theory would be very helpful. So please in later future try to make vidoes on graph related problems.
yes please @Aditya bhaiya graph theory ke placement point of view se questions karwa dijiye.
yes sir please
Bro really incredible videos. DP has never looked so easy!
This is how a literally a concept should be explained.
Our college teachers should learn something from this.
Thank you so much Aditya bhaiya!
This is LC hard problem and i was able to find the pattern before you shared the solution or gave hints. Thank you for this.
That "mere bhai" gives me same feeling which my college friend used to say before teaching outside exam hall....
Beautiful explanation, I would like to add that the code for shortest supersequence is also a very simple variation of LCS.
//Code
#define s 1001
class Solution
{
public:
int solve(string X, string Y, int m, int n, int t[s][s])
{
if(m==0) //If one of the input is null just return the other string.
return n;
if(n==0)
return m;
if(t[m][n]!=-1) //Memoized matrix
return t[m][n];
if(X[m-1]==Y[n-1]) //Add 1 to the length since only one of duplicates will be added to the ans.
return t[m][n] = 1+solve(X, Y, m-1, n-1, t);
else //Add 1 to each case because the discarded element will also be added.
return t[m][n] = min(1+solve(X, Y, m, n-1, t), 1+solve(X, Y, m-1, n, t)); // or 1+min(solve(..),solve(..))
}
//Function to find length of shortest common supersequence of two strings.
int shortestCommonSupersequence(string X, string Y, int m, int n)
{
//Memoized Approach.
int t[s][s];
memset(t, -1, sizeof(t));
return solve(X, Y, m, n, t);
//Tabular Approach.
/*int t[m+1][n+1];
for(int i=0;i
WOW mindblowing explaination .. i wanna see you live wanna know about you ... keep putting your rays over us ,ADITYA
This is by far the most interesting channel on TH-cam to learn DP! What a great video!!
This series can make anyone fall in love with DP!
when you said "ab mai thak gya hu bolte bolte" depicts your great efforts that you are putting to make us understand the concept. ❣ salute brother.
14:25 "I hope tumne answer bol hi diya hoga ab tkk.......itna pdhane k baad"😂😂
Thank you so much bhaiya!!
Man the confidence that you have while saying ki "ab to tumne bol dia hoga" is huge!!!!
That is very great feedback loop that it creates....
Great content you are creating!
Printing the Shortest Common Supersequence is in 29th video in playlist. Thank you.
thank you
bina video dekhe with the help of previous vids solve krdia question. Leetcode hard dekhke dar lagta tha and aaj toh question majak laga.
All thanks to one and only Aditya Verma. Thank you bhaiya.
Kudos to your effort and brilliant approach which made hard problems easy and fun which was nightmare before. I wish every talented like you contribute like you did. Thank you so much I have been benefited a lot from your videos.
Bhaiya you are best teacher. I understood every vedios and didn't skipped any you explained in awersome way. God bless you.
python code: github.com/IamBirender/Dynamic-Programming/blob/master/Longest-common-subsequence/shortest_subsequence.py
Who else laughed very hard after listening "Ab mai thak gaya hu is concept ko padhate padhate" hahahaha. Your videos are incredible brother. Thank you :)
This series is definitely going raise the bar of Indian Coding standards. People will slowly start to fall in the beauty of DP and will use it more and more.
Problem statement padhte hi, leetcode par jaake code krdia iska solution...
Great series, started loving Dp becuse of you...
The explanation is, as usual, great but this will only give the length of the supersequence. The main problem statement is to print the common supersequence. For that, we can't use LCS directly, we have to make some changes to get that matrix that will be used to print the supersequence using the concepts from the previous video.
Initialization will be changed. If anyone of the string is empty then the length of the result will be the length on the non-empty string.
That's why ->
if (I == 0) dp[i][j] = j;
else if (j == 0) dp[i][j] = I;
Now, if the current characters are equal then it's obvious to increase the length of the result by 1. Otherwise, we have to find the min length of sequences for two cases -> when ith character of string 1 is included and when jth character of string 2 is included.
Here's the code for the dp matrix -
int dp[s1.length()+1][s2.length()+1];
for (int i = 0; i < s1.length()+1; i++) {
for (int j = 0; j < s2.length()+1; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = 1 + dp[i-1][j-1];
} else {
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]);
}
}
}
}
Thanks for this reply, thought of the same solution before he related it to LCS!
15:47 that "Shortest wortest jaay bhaad me" cracked me up man. Lmaoooo
after watching Aditya Verma..
where I've been before??
thank you bhaiya.
You have really created interest in me from dp.
You have made things simple and easy to understand.
Thanks a lot for everything brother!!!
Bade Bhaiya love u 🥰🥰🥰🥰🥰🥰 ... Maine almost 60%+ playlist Dekha hu ... Life Ka sabse Acha programming playlist 💞💞💞💞💞💞💞 ... Bhaiya time apko time mile to aur bhi videos upload kijiyega ... It's super amazing 😍😍😍😍😍😍😍❤️❤️❤️❤️.. great love from banglore Bhai 🥰
Thanks brother, will be uploading soon !! And thank you for so many heart emojis ❤️😅, Please consider sharing among your friends to help the channel grow. Thanks for watching !!
@@TheAdityaVerma I am glad to hear that. If you could let us know what all topics you're planning to upload, that would be helpful. I check the notification daily to see if you have uploaded any videos or not.
I just want to say, this is amazing series on DP
Pure gem💎💎
Thank you for this golden playlist bhaiyya❤
Brother let me just say, you have a talent. I couldn't see this at all, and aftet you explained this, it just clicked and made so much damn sense.
For creating the supersequence:
1. FInd out the what is the longest common subsequence (find the string)
2. now iterate over the LCS and in the resultant string add all elements from s1 and s2 to the left of LCS[I]
3. Do this for every element of the LCS and at last, add the characters which are left from s1 or s2.
This method will ensure that order of the strings is maintained and the common characters are used only once
not clear
@Kartik Kalia 😂
That sudden formula we created made the problem 1 second 💎💎
Please bring the playlist of graphs,trees,greedy algorithms ,divide and conquer algorithms, linked lists, hashmaps and backtracking also bhaiya 😇 btw this dp playlist is best on youtube !
bhai jaisa tm padha rahe ho naa .. College ke teacheron ka sirf Bed Tea dene ka hi kaaam rah jaega..LOLOLOLOL
Best teacher ever, now I am getting the solution by just a little hint, all credit to Aditya sir 🤩🤩
Thank you sir for your amazing explanation. Your playlist for recursion and DP is very helpful . Again thanks a lot for these video.
Till 3:22 i was getting a strong sent of LCS and at 8:37 you confirmed it this is only because of you really thankyou bhaiya ❤❤❤
You following the new teaching style by using example(and that is extraordinary) but u still reading newspaper in the morning 😋
and how u got time to reading the newspaper before going the college 😜.By the way I lost one thing due to this DP playlist and that is hype of DP and this is really good so again Thank you.
Bhai ksm se bht achha pdhate ho yaar .. mujhe dp bht hard lgti thi lekin apka video dekh rha hu continue .. ab bht kuchh shikh gya hu .. atleast dp ka koi problem ab mil jaye na to km se km usko ab smjh kr or coding kr skta hu thanks bro❤️❤️❤️❤️
bhai 1 number.........................................................kya padhate yar tum.
you made it very simple bhaiyaaa!!!!!
i was thinking dp is the hardest thing in competitive programming, but after seeing your lectures, i realises that its not that hard..
thankyou......
bravo !!! just by looking at the input strings i was able to figure out the approach and my o/p was bit different -> len(LCS) + len(s1-LCS) +len(s2-LCS) Which eventually becomes len(s1+s2)-len(LCS)...Awesome video 💟
Aditya Bhaiya you are god... lot's of respect and love for you
Please make a video for the Longest Increasing subsequence problem!!
my mind is blown bro🤯🤯🤯...mouj kar di bhai
Thanks To Bollywood and Doraemon Cartoon, I learned HINDI in childhood for these. What A channel it is. You are a GEM brother.Respect
Note to self - There might be multiple LCS between two strings, but the SCS reconstruction would still work as our goal is to minimize the SCS. If we combine both strings directly, we can minimize its length by using any LCS to shrink the combined string. Since the length of all LCS sequences is the same, they would shrink the directly combined string equally while preserving the sequence.
this playlist is a gold mine !!
Q. What if there are say 3 or 4 strings? How will the complexity change?
Bhaiya, your way of explanation is the besttttt !!🥺🥺
people said DP is hard so i am also assume its hard and start your dp playlist from start but there is not a single point i realize that dp is tough you taught dp very easy and interesting way, So thnk u sooo much aditya for provide such a amazing content, i am always thnkful to you.
Bro your videos are like top notch. All I can do is if at all I get any ads, I'll do not skip them. Atleast this way I can help you get the max payment of that ad. Love you bro
seriously bro u are just awesome u have provided the quality content for free .Respect (100) .Thanks a lot learned whole dp from you
You are a gem ✌️
Superb Aditya....! What an explanation brother...! World-Class Teaching...! Solid DP Playlist...! Keep it up..!
aise question dhek ke fatti thi ab bacho wale lagte h good work bro
I solved this problem immediately with the knowledge of lcs after you explained it till 3:40
Bhaiya ne motivate kiya toh sach mai observe kar liya😎😎😎😎😎😎
Boss you are great!!!!!
MANITIAN🙂🙂✌️
aye nigga you here :)
boss manit se hai kya?
Oh my god, the way of explanation is lit, thanks!!🙌
Thanks Aditya bhai, It was very helpful and the way of teaching this series very much systematic i have ever seen.
Thanks sanjay for watching !! Also do share with your friends and college
God bless you for sharing so much of knowledge !! Truly valuable content :)
I solved this on my own in 10th minute you are great buddy
I was able to think about the solution before you shared the solution
best explanation🙏🙏🙏🙏
It's very very enlightening.
Thanks brother I am glad it helped you ✌️✌️, Share and help this channel grow, Do share !! just dont see this text and keep on watching the videos.😂😂😂😂
God ho bhaiya aap Dp ke Love from NITW
Bhaiya, can you please upload video of how to print the Shortest Common Supersequence?
Its something at next level
such a gem soln and teacher
Bhaisahab maza aaagaya what a explanation 😍😍
Nahi techer ko nahi bolenge for bed tea, thanks a lot aditya, really brilliant channel!!!!! 🍩
very nice explanation
You could be the top professor, I never saw someone have reduced the DP to DUST.
honestly..u are a really great teacher...i never thought..ki mujhe kch smj m bhi aayega..but after your..videos I am actually able..to solve..it(can't believe I am not scared of dp now)..well..keep going..and please make videos on trees and graphs too😅
The way he says "thanks" at last... xD
you really teaches good plz continue teaching .subscribed your channel..god bless
(A union B) = A + B - (A intersection B)
Best DP course on internet!
maan gaye verma sahab 🙏
Thank you very much. You are a genius.
5:05 😂😂😂
😅😅
Teacher aaye to bolo usko ki mereko bed tea do is opppppp 🔥🔥🔥🔥😂😂😂😂😂😘😂😂
Kya gazab padhate ho bhaiya aap 😁🙏
take my bow🙇🙇
this is like the venn diagram problem if you look it like that
Printing that supersequence would be a little tough though.
Just wait and watch 😅 its the 29th video, do comment after watching it and let me know if you find it tough.
@@TheAdityaVerma Okay, it's like a spoiler for me😂 but it's a relief that you have made a video on it.
@@yuvrajoberoi7834 same feel
this video really helpful thank you so much brother...
why vidio 27 is private?