Longest common subsequence algorithm -- example

-----
Video explains how LCS (longest common subsequence) algorithm creates a table to determine an answer.
The longest common subsequence (LCS) problem deals with a question how to find the longest subsequence common to all sequences in a set of (usually) two sequences.

[@bigray712]

you should make more algorithm videos. you're really good at explaining.

[@backup3412]

Yes we need more

[@4blossoms]

Great explanation. My prof didn't teach it this way, but makes the dynamic programming solution so much clearer!

[@abdulwahabalhrbi4908]

8 years later and his solution is better than my prof😂

[@techvishnuyt]

@@abdulwahabalhrbi4908 same 😂

[@pchebbi]

Wonderful explanation! You are a great teacher!!!

[@shanekhantsoemoe4996]

Thank you so much! I want to see more algorithm videos from you as you're really good at explaining them!

[@princemaratas3531]

I know it's late but I want to give you a very big thanks. this video really helps me understand how to code the LCS. that I used in Undergraduate Research :)

[@ChiranjeevTapas]

can you teach this to my teacher too?? damn she made this so difficult to understand! Dhanyawad(Thank You)!

[@TheMoviesManX]

My teacher is the same !

[@anishkhanal5108]

Yo fckin same here...i hate my teacher

[@diandhonalciranjang222]

same with me, my prof is always make anything dificult..

[@desideriaionescu8693]

Hello! I stayed all day to read and understand this method, and nothing...then, I found your video and I have understood. It is the best explanation!! I will be happy if you will put the algorithm in C++, as soon as posible. Thank you a lot!!

[@shrikantlondhe]

Nice and quick explaination, thank you.

[@kanakanakanakanameki2055]

wow I understand this very easily. thanks. the other explanations are too complicated and I don't have much time to study lol

[@Nikhil88able]

u did a gr8 job!!... just took 8 mins and several questions of LCS SOlved...:)

[@bryantwalley]

This is good. Thanks for taking time to put it together.

[@camaulay]

Great! Very clean explanation. Thanks mate

[@gopeswarnamasudra8895]

please upload more videos on (dynamic and greedy) algorithms, You are a great teacher

[@josephkatsioloudes9101]

Thank you so much for this explanation, my teacher was for the κάτσαρα!

[@shivamkhandar5737]

Very easy and understanding method sir keep it on

[@עומריפיינגולד]

listen man , this is the best shoki in thw world i understand everything but shir doesnt understand but now she will understand so slozki is the world have a good night

[@sheriff2424]

Thanks bro you just saved my CAT tomorrow😇

[@animexd6394]

Thanks man it's great explanation of the algorithm i read some blog about it but they always make stuff complicated for no reason.

[@cheicktraore5062]

Ya vid help me a lot during my exam thank you so much 🙏🏿

[@santoshjoshi7890]

thank alot,Daniel Sodkiewicz very simple to understand

[@jackolaslock]

Thanks for this video. I needed to see it being done to really get it.

[@ShubhamGupta-dz5bn]

Perfectly done!! Helped a lot!!

[@dickyzuerst2828]

thank you so much sir, finally i can understand it more better

[@TheHappieCat]

This explains it so well!! Thank you!

[@kouamelan87]

nice you explained in a very simple manner. thanks

[@ghostfacekillerist]

Thank you for your video! Helped me before a test!

[@sohamc7402]

Great work i wish you did more videos :)

[@SmashedRadio]

You did well, sir. Very well. Thank you

[@Thushan44]

Thanks mate! This is gonna help me a lot in my exam tomorrow lol

[@hridoyth8866]

Thanks for such an awesome explanation

[@rachitranjan]

Thanks ..You made it super easy...

[@supriyamekala8805]

Superb Sir

[@PriteshParekh77]

Awesome explanation.Fount it very helpful. Thanks mate.

[@faken143]

Nice tutorial! Than you Daniel.

[@Pathorkuchimon]

if u go UP and LEFT its BCBA if u go LEFT and UP its BDAB 2 answers !

[@zubairshahri2588]

Tufayel Talha how to correct it then

[@tomm7273]

The algorithm only gives you one of the longest subsequences. If there are multiple, taking different paths will give different subsequences. If you want all of them, you must traverse all paths.

[@nguyenthanhdat93]

I think It is okay to have two answers as long as the solution is optimal (one of the longest sequences).

[@SnoozeDog]

good catch! There are only 2 answers if Left and Up are the same length and no diagonal exists on that entry. Since to get to that point you had to choose between 2 strings of equal length, thus both paths must be taken to derive answers

[@hootis8]

Great video, you explained everything very clearly, you saved my ass

[@anesp.a913]

Hi Dear Sir, A great work you have done , thanks alot Anes

[@roboarif]

Great work... I could not understand a thing when this was taught in class. But i understood perfectly here.. I m still confused why i could'nt get it in class :/

[@OneShotLegacy360]

Thank you. Saved my life.

[@i_dont_want_to_use_handle]

Thank you!!!!! 공부중에 LCS가 이해가 전혀 안 됐었는데, 덕분에 이해가 되었어요! 정말 감사합니다!!!

[@kopiro]

Great explanation. Thank you.

[@rakeshraih]

perfect, nicely done. you rock man

[@tonyzhangable]

Thank you! Very clear explanation!

[@HabiburRahmanHabibur]

Thanks and good work but I think ,there are 2 LCS is possible from the table you created. so, If you show all the possible LCS ,it will be good .

[@gianlucarosadini1163]

Dude you are the best... Thank you!

[@SRIHARSHAVARADA]

nice..! Easy to understand..!

[@piyushgoel3020]

Simple explanation. Thanks

[@dighechinmayt]

Thank you daniel.U made it easy

[@senthilkumaran7936]

Thank you very much, that was very lucid.

[@avibhav265254]

thanks alot....kindly teach my teacher if u can.....

[@richatiwari4043]

very nice explanation :)

[@boyadeng7127]

It's a great illustration.

[@tony-silver]

Nice explanation, thanks!

[@sruthysathyanandan7268]

thanku sir....u taught well

[@sakthivelpalanivelu3833]

Thank you so much. Very nice one.

[@sundusali9293]

very well explained. thank you

[@InvitusCode]

thanks for sharing, you saved my day! =)

[@parasmalhotra7633]

nice and concise..

[@Princebharti9971]

nice explanation !

[@prajaktadeosthali3083]

Thanks a lot for this video!

[@sumita913]

Thanks so much! this totally helped me understand!

[@mallikanaik14]

This was really helpful!! Thanks!!

[@babanparab2370]

thanks sir very nice explanation

[@punstress]

So the subsequence doesn't have to match exactly, just be in order? One has BDAB but the other has BDCAB.

[@DanielSodkiewicz]

Yes, you are correct

[@AdamAdam-yo3oh]

Such a great tutorial.

[@jenilgadani1491]

helped a lot..thanks for uploading it :)

[@pussio3950]

Simplicity at best, thanks

[@swarajingle7639]

awesome vid 👍

[@jmdryden]

thanks! super helpful.

[@amitavital]

Omg i love you its help me so much

[@BrimozDDdDdD]

very consise, much appreciated

[@hayaaaa9273]

Nicely taught

[@itishreesahu8745]

Thank u so much....👍👍

[@ragulkumarrajendran4251]

Nice one man

[@1SSW]

Hi there, are you able to do a video on Boyer Moore pattern matching algorithm with last occurrence table

[@markmontejo1726]

thanks for this video sir :)

[@hsuyusi8350]

thank you, it's a great video !!

[@SamraatMaharjan]

absolutely thanks bro

[@doosc]

Are the tracking results the same if I swap rows and columns?

[@shubhamupadhyay4695]

thanks a ton man..This helped alot.

[@lucumu]

another awser is BCBA，Which one should we choose?

[@Melaf90s]

Think you so much

[@maphioso]

thank you so much !

[@semirek]

Thanks a lot!

[@shocolate0104]

Thanks! found it helpful!

[@LUX1111111111111]

just curious did u film it with ur cellphone

[@DanielSodkiewicz]

LUX1111111111111 indeed :)

[@guywithspectacles]

THANK YOU SO MUCH MAN YOU ARE LOVE YOU ARE LIFE... COZ U JUST SAVED MY ASSS FROM FAILING XD

[@md.shafaatjamilrokon8587]

thnks.lve frm Bangladesh

[@horsefeather]

Why does the LCS of ABCB not work as well? I also noticed that you found this exercise in the Introduction to Algorithms textbook which I am currently using for my course.

[@DanielSodkiewicz]

yes, there are few correrct solutions

[@PaTTaMoNE]

Thank you for your video. I am very grateful. You have helped a lot. :D

[@dhhsncnd6107]

The logic is simple here, let LCS [i,j] represent longest common substring of a[1...i] and b[1..j]. if (a[i] == b[j]) LCS[i,j] = LCS[i-1,j-1] + 1; else LCS[i,j] = max(LCS[i-1,j], LCS[i,j-1]);

[@donovankeating8577]

Why do we have to get the max of L[i-1][j] and L[i][j-1] if no commonality is found? Is it because of the 0's in the first row and column? Because for other cases, the max is always the cell to the left. Am I right?

[@sakuray7]

Thanks!!!

[@tartacalin7732]

Thank you.

[@gioduduchadze2430]

couldn't we go from ones to zeroes on CB? there was a bridge over there or if there's a chance to go left or top we should use it always?

[@DanielSodkiewicz]

When you start in the corner, you decide if you will follow a pattern left top , or top left and you follow that for the entire journey, To answer your question: if you can go left or top - yes, you must go this direction.

[@MdSazzadulIslamsazib]

Nice one :)

[@kshitizadhikari3855]

awesome !!thnks :)

[@theess1248]

Thank you

[@Beesh29]

thanks 🌷

[@SaurabhGupta-bl5bb]

Nailed it !