24 Shortest Common SuperSequence

[@purandarparitosh]

I can't believe we are getting all this for free! Pure Gold! Thanks a ton, bhaiya! :) :)

[@TheAdityaVerma]

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.

[@tarunreddy8243]

@@TheAdityaVerma i done it 3000 times bhai

[@pruthvirajk6019]

@@tarunreddy8243 Eh ooru mandi

[@kongzilla2897]

@@pruthvirajk6019 me hyderabad

[@hemantmangwani1006]

@@TheAdityaVerma Bhai I have shared in all of my college coding club Groups of every year. Keep Making More Videos.

[@suvitsharma7432]

@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 !!!

[@ka_ka3141]

pinch

[@kartikeshwarhingole6007]

Han bhai

[@beinghappy9223]

Same here

[@rjesh2062]

Not bragging but mereko toh prblm statement padhne se hi pata chal gya Aditya Sir OP

[@bingikarthika]

Same here

[@tiyashadas5247]

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!🌻

[@TheAdityaVerma]

Thanks Tiyasha 😅 I am glad that you answered that correctly !! And yeah thanks for the sunflower !! 😂😂

[@tiyashadas5247]

@@TheAdityaVerma 😂 You're welcome!

[@bhavyapandey]

Exactly same bhai :')

[@AmanSharma-li7ct]

@@adhishmalviya2408 Nhi milega Sunflower ke liye Thanks XD

[@kunalbahirat7795]

@@TheAdityaVerma men will be men

[@rahulsawhney]

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; }

[@messi_codes]

Thanks

[@AmanSharma-or5vh]

Beautiful code

[@jaxsriv1052]

Last loop while(i>0) is not clear. Can you please tell why is that done.

[@spandanbasu_1228]

Perfect.. was just looking for it!! Thanks man😊❤

[@spandanbasu_1228]

@@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!

[@ShreyaSingh-vr9qi]

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 !!

[@TheAdityaVerma]

Thanks for watching dude !! ✌️❤️

[@AvikNayak_]

@@TheAdityaVerma please make a playlist on graphs also.

[@competitivedoritos4294]

teacher: so everybody open the book and head to page numb... aditya: pehle bed tea do [5:05 time stamp reference]

[@mickyman753]

i can somehow imagine him asking for a bed tea from the school teacher

[@yogeshyts]

@@mickyman753 ab school ke bache se dp padhenge btech wale

[@mickyman753]

@@yogeshyts arey whitehat Jr. ke ad main Chintu app bna rha hai , toh phir school ka baccha bhi dp kr hi lega

[@yogeshyts]

@@mickyman753 😂🔥 Btw which clg?

[@mickyman753]

@@yogeshyts sgsits,indore , you?

[@dsa9980]

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..!!

[@sayantanbanerjee821]

14:25 Twist of the century! :jaw_dropping:

[@0anant0]

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!

[@nikhilpatil2482]

same

[@jaswanthsabbisetti6820]

I improved understanding of Hindi and DP after watching these :)

[@sanjayvasnani988]

This playlist is making me fall in love with DP.

[@neildahiya2524]

Bro really incredible videos. DP has never looked so easy!

[@jhalamaan]

WOW mindblowing explaination .. i wanna see you live wanna know about you ... keep putting your rays over us ,ADITYA

[@ranjeet5806]

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.

[@ayushsrivastava9932]

nice explanation. I concluded that its basically n(AUB)=n(A)+n(B)-n(A ∩ B)

[@aryananandsinha843]

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.

[@priyarani9569]

But it is for sets not for strings because.. A String can contain duplicate letter

[@tusharsaxena8239]

@@priyarani9569 exactly

[@gaunikasrivastava7851]

@@priyarani9569 Also not necessarily A intersection B contains the common letters in the same order. That's also a reason.

[@abhinandanb3591]

puluthi

[@akash-yh8kb]

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.

[@devanshmesson2777]

This is how a literally a concept should be explained. Our college teachers should learn something from this. Thank you so much Aditya bhaiya!

[@saliq0097]

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.

[@bhawna1997]

This is by far the most interesting channel on KZbin to learn DP! What a great video!! This series can make anyone fall in love with DP!

[@arafathbaig841]

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.

[@bhavyapandey]

yes please @Aditya bhaiya graph theory ke placement point of view se questions karwa dijiye.

[@ayushvats1808]

yes sir please

[@adityaperiwal4819]

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.

[@yuvrajoberoi7834]

Ha bhai apna selection hne ke bad par😂

[@raviashwin1157]

@@yuvrajoberoi7834 bhai yeh bol bol kar sabko scheme bata dega😹

[@yuvrajoberoi7834]

@@raviashwin1157 bhai 25 din ke andr selection lelo😂

[@raviashwin1157]

@@yuvrajoberoi7834 🤣

[@anmolsharma9539]

@@raviashwin1157 ashwin bhai aap cricket khelo yha kha aa gye 😂

[@keshavraghav3896]

Problem statement padhte hi, leetcode par jaake code krdia iska solution... Great series, started loving Dp becuse of you...

[@chetannikam8129]

bhai 1 number.........................................................kya padhate yar tum.

[@pizzazzguy]

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]); } } } }

[@shashanksarma4096]

Thanks for this reply, thought of the same solution before he related it to LCS!

[@aakanshasoni5798]

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.

[@vishalsethi4024]

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!

[@hashcodez757]

14:25 "I hope tumne answer bol hi diya hoga ab tkk.......itna pdhane k baad"😂😂 Thank you so much bhaiya!!

[@nayan7065]

Bhaiya you are best teacher. I understood every vedios and didn't skipped any you explained in awersome way. God bless you.

[@udaytewary3809]

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 ❤❤❤

[@sourabhzambre2105]

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 💟

[@ajeetpatel7991]

after watching Aditya Verma.. where I've been before?? thank you bhaiya.

[@adarshsasidharan254]

Printing the Shortest Common Supersequence is in 29th video in playlist. Thank you.

[@AemondTargaryen_]

thank you

[@shree1365]

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❤️❤️❤️❤️

[@manavshah7450]

You have really created interest in me from dp. You have made things simple and easy to understand. Thanks a lot for everything brother!!!

[@abheykalia3409]

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

[@Adarsh-mn7pl]

not clear

[@prabalsrivastava9808]

@Kartik Kalia 😂

[@pranayprasad50]

Best teacher ever, now I am getting the solution by just a little hint, all credit to Aditya sir 🤩🤩

[@arpitparmar2121]

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 :)

[@AnupBarman-bd1ju]

15:47 that "Shortest wortest jaay bhaad me" cracked me up man. Lmaoooo

[@pradeepmondal4943]

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 🥰

[@TheAdityaVerma]

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 !!

[@indranilthakur3605]

@@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.

[@durgeshkushwaha2534]

I just want to say, this is amazing series on DP Pure gem💎💎

[@soumikmukherjee4797]

Aditya Bhaiya you are god... lot's of respect and love for you

[@RandomShowerThoughts]

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.

[@avinashmodi5230]

That "mere bhai" gives me same feeling which my college friend used to say before teaching outside exam hall....

[@shashankmishra4079]

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.

[@sharuk3545]

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.

[@pandavgupta1427]

Thank you sir for your amazing explanation. Your playlist for recursion and DP is very helpful . Again thanks a lot for these video.

[@sohebshaikh3344]

Bhaisahab maza aaagaya what a explanation 😍😍

[@kailashjangir1530]

my mind is blown bro🤯🤯🤯...mouj kar di bhai

[@joshithmurthy6209]

this playlist is a gold mine !!

[@cripz4203]

Q. What if there are say 3 or 4 strings? How will the complexity change?

[@adarshsinghkushwaha6770]

i was thinking dp is the hardest thing in competitive programming, but after seeing your lectures, i realises that its not that hard.. thankyou......

[@sambhavi6141]

Bhaiya, your way of explanation is the besttttt !!🥺🥺

[@harshshukla7675]

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.

[@gandhijainamgunvantkumar6783]

I solved this problem immediately with the knowledge of lcs after you explained it till 3:40

[@VIVEK1898]

Please make a video for the Longest Increasing subsequence problem!!

[@shubhamchaudhary8688]

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.

[@TanviNaik-bl2od]

Thank you for this golden playlist bhaiyya❤

[@ghosted19282]

you made it very simple bhaiyaaa!!!!!

[@LokeshPandey-m1m]

such a gem soln and teacher

[@herculean6748]

Oh my god, the way of explanation is lit, thanks!!🙌

[@vaibhavkumarjha7771]

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 !

[@shubhamshah3023]

For the same question, agar input mein we have more than 2 strings aa jaaye to uska approach kaise rahega ? like we cannot solve it with DP right. Iteratively string merge kare to complexity badh jayegi ? So usko kaise approach karenge ?

[@workandearnwithshubhi9050]

Bhaiya ne motivate kiya toh sach mai observe kar liya😎😎😎😎😎😎

[@adityan5302]

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

[@sarcasmtube69]

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😅

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@medhashree2416]

Kya gazab padhate ho bhaiya aap 😁🙏

[@GamingEver07]

aise question dhek ke fatti thi ab bacho wale lagte h good work bro

[@optimistic_dipak8632]

Superb Aditya....! What an explanation brother...! World-Class Teaching...! Solid DP Playlist...! Keep it up..!

[@aishwarya1895]

You are a gem ✌️

[@rajatgupta7488]

(A union B) = A + B - (A intersection B)

[@shivankchaturvedi4817]

seriously bro u are just awesome u have provided the quality content for free .Respect (100) .Thanks a lot learned whole dp from you

[@sabujjana2860]

It's very very enlightening.

[@TheAdityaVerma]

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.😂😂😂😂

[@sonurathod9551]

you really teaches good plz continue teaching .subscribed your channel..god bless

[@AkkumBakkum-m5h]

solving striver a2z sheet with your approaches next level aderaline hitting

[@baravkarnishithjagdish-iii5945]

maan gaye verma sahab 🙏

[@sanjaychaudhary4673]

Thanks Aditya bhai, It was very helpful and the way of teaching this series very much systematic i have ever seen.

[@TheAdityaVerma]

Thanks sanjay for watching !! Also do share with your friends and college

[@NotFound-hy7qb]

I solved this on my own in 10th minute you are great buddy

[@mayurkoli4145]

Boss you are great!!!!! MANITIAN🙂🙂✌️

[@sumitkumarverma313]

aye nigga you here :)

[@sumitkumarverma313]

boss manit se hai kya?

[@shrutikakarande5441]

God bless you for sharing so much of knowledge !! Truly valuable content :)

[@KrishStocks]

it can be done in O(n), use map for 1string store char and count use another map for string 2, now iterate over any map, assume we are iterating over 1st map, then see that character also present in 2nd map is take the max of that and add it to ur ans and erase that character from both the maps, after iterating completely then again iterate over 1st map and see if anything is remaining then add all and iterate over string 2 and add all the count, thats it done😅😅

[@vaaidooyt1837]

@Aditya Verma Sir why you stopped posting videos on this channel

[@joichirogaming]

That sudden formula we created made the problem 1 second 💎💎

[@sabbirhossain2132]

this video really helpful thank you so much brother...

[@priyarathore9266]

Best DP course on internet!

[@diveshrajput572]

bhut shandaar,bhai

[@muntasir4600]

Thanks To Bollywood and Doraemon Cartoon, I learned HINDI in childhood for these. What A channel it is. You are a GEM brother.Respect

[@KhushiNautiyal-pk5re]

best explanation🙏🙏🙏🙏

[@mayurrajbharati872]

Bhaiya, can you please upload video of how to print the Shortest Common Supersequence?

[@vanshchaudhary8291]

very nice explanation

[@parthdeshwal4419]

solution starts @8:22

[@PeaceLoveAman]

14:23 iss baat ka dard hum samjh sakte hai! 😂😂😂😂

[@danishakhtar2683]

God ho bhaiya aap Dp ke Love from NITW

[@messi_codes]

how to print this " Shortest Common Super sequence "?

[@navneetkaur4125]

You teach so amazing!

[@qR7pK9sJ2t]

bhai jaisa tm padha rahe ho naa .. College ke teacheron ka sirf Bed Tea dene ka hi kaaam rah jaega..LOLOLOLOL

[@beerauppamnaveenteja720]

Can I get any good reference to learn the basics goodly for Graphs, Bit manupulation and Greedy Algorithms?

[@ravilamkoti5081]

maza aa gaya bhai mainay code may khud say implement kar diya

[@ArunSethia]

awesome explanation.

[@preetambal7443]

I am trying to figure out the algorithm to print the shortest common supersequence..Can you please help me with that?

[@amithbhat1782]

same method as printing the LCS, just you have to add the character with lesser value of T in the array string : like this : if(T[i-1][j]

[@preetambal7443]

@@amithbhat1782 thanks 🙏

[@amithbhat1782]

nvm, video is already uploaded.... didnt notice(number 29 of DP series)