Longest palindromic substring | Dynamic programming

Рет қаралды 387,453

Күн бұрын

This video explains how to find longest palindromic substring from a given string. This is a very frequently asked programming interview and coding round question. I have explained two techniques here. One is bruteforce by generating all possible substrings and checking if it is palindrome or not and storing the longest substring which is a palindrome found. My audio quality is bad due to damaged-mic so kindly bear for this video. 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 :)
CODE LINK: www.geeksforgeeks.org/longest...

Пікірлер: 479

@techdose4u 9 ай бұрын

🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: +91 8918633037 🔴 𝐂𝐡𝐞𝐜𝐤𝐨𝐮𝐭 𝐚𝐥𝐥 𝐨𝐮𝐫 𝐂𝐨𝐮𝐫𝐬𝐞𝐬: techdose.co.in/

@ragas_ 4 жыл бұрын

Fact : This guy alone is responsible for more placement offers than all college professors combined ! Change my mind

@techdose4u 4 жыл бұрын

Thanks

@ankitparashar8730 2 жыл бұрын

Professor kaha padhata Sab chutiyapa hai professor

@prajwalraut7480 Жыл бұрын

woahhhh today also this one is best explaination!!!!!!!!!!!!!!

@KevinLin45 Жыл бұрын

🧠 yelo change krlo :)

@hey............. 4 жыл бұрын

Kudos for going through the whole input string instead of saying so on and so forth👍

@techdose4u 4 жыл бұрын

😂

@lionelmesssi2959 3 жыл бұрын

Bro tomorrow my exam is there , exam will consist of coding question in Java. Dynamic programming also there can you help me for exam .

@tekbssync5727 3 жыл бұрын

@@lionelmesssi2959 I don't think there will be any football match tomorrow .

@ganesh3761 2 жыл бұрын

@@tekbssync5727 😅😁

@jrajesh11 2 жыл бұрын

What a great presentation and explanation ! You are just going frame by frame and bringing clarity all the way down deep! Keep doing such great videos for demystifying complex algos.

@thecritiquer5976 11 ай бұрын

I knew from reading other explanations that it was the explanation itself that was hindering everyone including myself. You are so far the only person that actually explained how the dynamic approach works clearly.

@KushalBhatia 3 жыл бұрын

Please give this man a medal. Thank you for going through the whole string dry run

@aslanfeng413 4 жыл бұрын

THE best explanation I’ve heard so far!!!

@techdose4u 4 жыл бұрын

@lionelmesssi2959 3 жыл бұрын

Bro tomorrow my exam is there , exam will consist of coding question in Java. Dynamic programming also there can you help me for exam .

@sathvikrijo 4 жыл бұрын

One of the best explanations for this question, for dp beginners🎉🍾 thanks a lot man💐👍

@sam_s3344 3 жыл бұрын

Thanks a million for making such an incredible explanation for a GFG code. Sometimes they have good codes, but no explanations or the explanations are not clear enough. This is just so well explained. All your videos are helping so many of us. Keep up the great work!

@techdose4u 3 жыл бұрын

Welcome :)

@yuganderkrishansingh3733 4 жыл бұрын

Bro this is the best explanation for the question and I finally understood it. Explaining is an art and making others understand is a superpower and you clearly has it. The video was crisp and so easy to follow. Just loved it. Pls keep making more videos. I know you might be busy with other stuff(I am sure u might be working for some top notch company and if not then you are surely going to be very soon) but pls keep making more videos.

@techdose4u 4 жыл бұрын

Yea sure :)

@bookalicious9849 3 жыл бұрын

Excellent explanation ! As a newbie in dp i really was struggling to understand this concept but you made my life easier !!!

@techdose4u 3 жыл бұрын

Thanks

@utkarshsrivastava7885 3 жыл бұрын

You are just explaining the whole concept with patience . thanku for clearing me this algo ,you are just my fav man❤️

@techdose4u 3 жыл бұрын

Welcome :)

@ayeshaadhikari6123 2 жыл бұрын

No amount of thanks is ever going to repay the help you're lending us :) Thanks a tonne sir! Keep growing

@paulcurran3661 3 жыл бұрын

Thank you for this, I've had trouble understanding this algorithm in other videos but this is the best explanation I've seen.

@techdose4u 3 жыл бұрын

Thanks :)

@chillegaming8250 3 жыл бұрын

This is gold! Thank you for that clear explanation.. your DP series is the best out there!

@techdose4u 3 жыл бұрын

Welcome ❤️

@meetmodi2487 3 жыл бұрын

New to DP. Was trying to get this approach for 2 hrs.Thanks alot for the explanation.Explained so well,no need to upload the code!

@ajeetshankar7946 2 жыл бұрын

Quality content with best explanation compared to every other video, special thanks to you!!

@JSInstructor 3 жыл бұрын

Thank you so much for the video! I hadn't truly understood the dynamic programming approach to the max palindrome substring problem until I watched your explanation. Thanks again!

@techdose4u 3 жыл бұрын

Welcome :)

@abhishekbaral4699 3 жыл бұрын

really understood the concepts of DP with clarity. Never visualized like this before.. Thanks

@manojrajasekar6035 4 жыл бұрын

Best Explanation ever ! Please continue doing this. Thank you :)

@techdose4u 4 жыл бұрын

Yea..... Thanks :)

@omerfarukbuyukbas 2 жыл бұрын

It is really the best explanation I've ever seen in this subject! Thank you!

@abdallaalhag4425 5 ай бұрын

I really love how you draw and go through the DP table. I don't see many people explain it that way and it can be very hard to visual or trace through at first. Thanks So much!

@jaatharsh 3 жыл бұрын

Thanks, TechDose, crisp n clear explanation, exactly what I was looking for, keep uploading!

@techdose4u 3 жыл бұрын

Thanks

@9669sumit 2 жыл бұрын

Now i know why your video is on the top when searched for this problem. Thanks for such good content.

@prasitamukherjee5864 4 жыл бұрын

Thank you so much! It was crystal clear.

@ayyappareddy4461 2 жыл бұрын

I watched lot of videos for this problem but no one explained like the way you explained.thank you sir

@tigerbear3038 2 жыл бұрын

Excellent explanation! Really appreciate that you went step by step even though it seemed tedious but it made it easy to follow.

@techdose4u 2 жыл бұрын

Thanks ☺️

@TravelWithAmitDubey 4 жыл бұрын

I liked the way you explained this problem, best explanation I ever found for this problem.

@techdose4u 4 жыл бұрын

Thanks :)

@harshitbhatt5875 3 жыл бұрын

Please, if possible, explain how you approach a problem and come up with solutions too as it'll help in developing our programming logic as well. Thanks for the great vids, keep em comin'! :)

@techdose4u 3 жыл бұрын

Sure :)

@atefnazi753 3 жыл бұрын

How you explain these things so clearly..... I must say you are very underrated

@PujaKumari-rp5sg 2 ай бұрын

If I had a teacher like you during college, I would never doubt myself that I can't learn DSA.

@aakashparmar560 2 жыл бұрын

God-level explanation.!! If possible please keep these videos coming.

@ZiadGholmish 4 жыл бұрын

Honestly, the best one explained this question

@techdose4u 4 жыл бұрын

Thanks :)

@satvik_b Жыл бұрын

good explanation! The reason this is a dp problem is that it has over lapping sub problems. For substring from index 1,5 we need to check if substr from index 2,4 is palindrome or not and for substr 0,6 we would not compute for substr 1,5. So it will take O(1) time instead of O(n).

@krithickkrishnagiri6371 4 жыл бұрын

finally got the concept behind the dynamic programming. Thank you

@techdose4u 4 жыл бұрын

Welcome :)

@lionelmesssi2959 3 жыл бұрын

Bro tomorrow my exam is there , exam will consist of coding question in Java. Dynamic programming also there can you help me for exam .

@shrutibansal5261 2 жыл бұрын

best video I have seen so far for understanding dp using a table

@beautifultime9031 4 жыл бұрын

The only video that explains the DP matrix and each step of the algorithm. Thanks so much.

@techdose4u 4 жыл бұрын

Welcome :) I always explain the intuition and steps of dp matrix with reason for formulations.

@arjunreddy3615 4 жыл бұрын

Explained very well.. I have written the code using the instructions and it is working well strings of random sizes.. Thank you...

@techdose4u 4 жыл бұрын

Welcome :)

@mychannelyashi2441 3 жыл бұрын

This channel is now becoming my fav channel,,, thanks for explaining the concept so easily .

@techdose4u 3 жыл бұрын

Welcome :)

@lionelmesssi2959 3 жыл бұрын

Bro tomorrow my exam is there , exam will consist of coding question in Java. Dynamic programming also there can you help me for exam .

@darshansimha2166 3 жыл бұрын

The best explanation so far!

@sakshiramsinghani5284 3 жыл бұрын

Thanks a lot, you've explained it really well. It's very helpful.

@techdose4u 3 жыл бұрын

Welcome :)

@guruvigneshnagaraj8501 4 жыл бұрын

Perfect Explanation. Thank you!!

@techdose4u 4 жыл бұрын

Welcome :)

@shubhammahindru3563 9 ай бұрын

This is the best expalantion for this question on youtube, thanks mate

@Star_Bawa9 2 жыл бұрын

Thanks , you get straight to the point continue like this

@0laoye 7 ай бұрын

what a great explanation! love your divide and conquer techniques

@radhu8 3 жыл бұрын

Can't explain how thankful I am for your explanations!

@techdose4u 3 жыл бұрын

Welcome :)

@lionelmesssi2959 3 жыл бұрын

Bro tomorrow my exam is there , exam will consist of coding question in Java. Dynamic programming also there can you help me for exam .

@rajeshseptember09 2 жыл бұрын

outstanding explanation man !!! Keep up the great job !

@gmdz0ji336 4 жыл бұрын

Best explanation ever!! Thank you sooo much :D

@techdose4u 4 жыл бұрын

Welcome :)

@satweek123 4 жыл бұрын

Really good explanation @techdose. i feel more confident with DP now

@manishbolbanda9872 Жыл бұрын

wow this is gold. such a great solution. Thanks a ton. i usually approach dp problem with rec first then memoization then tabulaiton. bt this is more like concrete tabulation solutiion.

@prateeksrivastava1577 3 жыл бұрын

One of the best explanation for this problem.....Thanks bro...!!!!

@AmazingWorld-fw9oc 3 жыл бұрын

I'm glad I found this channel.

@techdose4u 3 жыл бұрын

😊

@HarinathSrinivas 4 жыл бұрын

For length 3 also it is enough to check only if characters are equal, like length 2 as diagonal is always 1.

@dattatreyapujar4068 4 жыл бұрын

Nice work. Hope to see your channel grow beyond numbers.

@techdose4u 4 жыл бұрын

Thanks buddy :)

@CodeSuccessChronicle 3 жыл бұрын

thanks for going through the whole string. Thank you for all your efforts 🙏

@techdose4u 3 жыл бұрын

Welcome :)

@lionelmesssi2959 3 жыл бұрын

Bro tomorrow my exam is there , exam will consist of coding question in Java. Dynamic programming also there can you help me for exam .

@AbhishekA-81 3 жыл бұрын

One of the best teachers found on KZfaq 👍🏻

@techdose4u 3 жыл бұрын

Thanks :)

@piyusgupta9498 4 жыл бұрын

Awesome explanation, finally I understood, thanks.

@techdose4u 4 жыл бұрын

Welcome :)

@msreenivasaprasad2214 4 жыл бұрын

Very clearly explained . Thanks for helping me out brother.

@techdose4u 4 жыл бұрын

Welcome

@ashwinraj8918 4 жыл бұрын

Flawless explanation!!. Thank You!

@techdose4u 4 жыл бұрын

Welcome :)

@pathevolutionnetwork 3 жыл бұрын

This was great !! Thanks for helping me understand this one

@techdose4u 3 жыл бұрын

Welcome :)

@pavanrao5896 4 жыл бұрын

One of the best explanations I've come across! Do you have a video for O(n) complexity as well?

@techdose4u 4 жыл бұрын

No, till now I have not made any video on manacher's algo.

@sanskaripatrick7191 2 ай бұрын

best explanation of this dp problem. Thank you so much🙏

@collins4359 2 жыл бұрын

thanks for the explanation. was so good I didn't need help writing the code.

@Surya-np1bb Жыл бұрын

Awesome buddy! Thanks for this

@saicharanpinninti548 5 ай бұрын

very good explanation and this was my first dp problem really understands really well

@hassaankhalid873 2 жыл бұрын

This was great, sir. Thank you.

@shubhamsinha5664 4 жыл бұрын

if there are more than one substring of the same length then how to return the substring which occurs first ( with the least starting index ) ?

@jhilikkundu3158 3 жыл бұрын

Noone says that row is the starting pos and column ending. You just clear my doubt in first few minutes. Thank you again.

@techdose4u 3 жыл бұрын

Welcome :)

@bhumberg3243 3 жыл бұрын

The BEST explanation ...tqsm

@harshpanwar1550 3 жыл бұрын

Thank u so much sir.....You explained in a wonderful way!!!

@techdose4u 3 жыл бұрын

Thanks

@rahul88632 Жыл бұрын

Thanks for simple explanation

@deveshagarwal660 4 жыл бұрын

Amazing video and nicely explained. Great job

@techdose4u 4 жыл бұрын

Thanks :)

@Star_Bawa9 2 жыл бұрын

That was a brilliant Explaination...

@sureshgarine 2 жыл бұрын

very nice explanation. thank you

@sangramkesharighosh1698 Жыл бұрын

Your explaining skill is mind-blowing 😁

@vancedaccount7951 Жыл бұрын

Thx for this Video man.

@anitapanda9267 3 жыл бұрын

Sir...how beautifully u explained the logic...Thank you

@techdose4u 3 жыл бұрын

Welcome :)

@kumarc4853 2 жыл бұрын

thank you Tech dose, I cracked google and linkedin. Learned a lot from your videos and explanations

@techdose4u 2 жыл бұрын

Congratulations 🤗💥🎉

@anukriti5648 2 жыл бұрын

Well explained ✨😃Thankyou..

@kentsang9376 3 жыл бұрын

Very nice explanation, thank you so much!!!

@techdose4u 3 жыл бұрын

Welcome :)

@ajayladhar731 2 жыл бұрын

thank you brother for detailed explanation

@bonagiripraneeth9502 3 жыл бұрын

Sir I didn't understand how to loop through the array, first we checked for (0,2) then for (1,3) and then for (2,4)... How to increment both I and j and after reaching end for j , we again set set I to some other index. How and which loops should be used?

@padmaraghunathan4849 3 жыл бұрын

Such a great teacher 🙏🙏🙏🙏🙏

@srinaath9845 4 жыл бұрын

Thank you bro. Awesome explanation 👏

@techdose4u 4 жыл бұрын

Thanks :)

@nikhilkaushal1615 2 жыл бұрын

Nicely explained! Thank you!

@techdose4u 2 жыл бұрын

Welcome 😀

@tanmaysatsangi131 3 жыл бұрын

Hello Tech Dose, can u please explain why this formula can't be apply for string length less than 3.

@siddhantgoswami6651 4 жыл бұрын

will you please make a conceptual video on manacher's algorithm with pseudocode, i am waiting for the same, thanku

@diasposangare1154 4 ай бұрын

the best explanation i found

@Mandeepsingh-jo5cf 3 жыл бұрын

Thanks man for these explanations.

@techdose4u 3 жыл бұрын

Welcome :)

@mikeerazo76 2 жыл бұрын

Wonderful explanation!

@crankyinmv 3 жыл бұрын

Thanks. Very useful. However, brute force can be done in O(n^2): for(0 through length of string-1) find the longest palindrome whose middle is in that position if(longer than the previous max) save the start and end indexes return substring at the saved start and end indexes

@geeteshchallur1034 2 жыл бұрын

So how is dp appoach better than this approach?