LeetCode 5. Longest Palindromic Substring (Algorithm Explained)

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow Me on X/Twitter - x.com/nickwhitereal
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering

[@AjaySingh-xd4nz]

Great Explanation. Thanks! Providing R - L - 1 explanation: e.g. racecar (length = 7. Simple math to calculate this would be R - L + 1 ( where L= 0 , R=6 )), considering start index is '0'. Now, in this example ( 'racecar' ) when loop goes into final iteration, that time we have just hit L =0, R =6 (ie. length -1) but before exiting the loop, we are also decrementing L by L - - , and incrementing R by R ++ for the final time, which will make L and R as ( L = -1, R = 7 ) Now, after exiting the loop, if you apply the same formula for length calculation as 'R - L +1', it would return you 7 -( - 1 )+1 = 9 which is wrong, but point to note is it gives you length increased by 2 units than the correct length which is 7. So the correct calculation of length would be when you adjust your R and L . to do that you would need to decrease R by 1 unit as it was increased by 1 unit before exiting the loop , and increase L by 1 unit as it was decreased by 1 unit just before exiting the loop. lets calculate the length with adjusted R and L ( R -1 ) - ( L +1 ) + 1 R -1 - L -1 + 1 R -L -2 + 1 R - L -1

[@kickbuttowsk2i]

thanks for your explanation, now everything makes sense

[@AjaySingh-xd4nz]

@@kickbuttowsk2i you are welcome!

[@amruthasomasundar8820]

Could you please provide the explanation of why start takes len-1/2 instead of len/2

[@AjaySingh-xd4nz]

@@amruthasomasundar8820 Start is calculated as (len-1)/2 to take care of both the possibilities. ie. palindrome substring being of 'even' or 'odd' length. Let me explain. e.g. Case-1 : When palindrome substring is of 'odd' length. e.g. racecar. This palindrome is of length 7 ( odd ). Here if you see the mid, it is letter 'e'. Around this mid 'e', you will see start ('r') and end ('r') are 'equidistant' from 'e'. Lets assume this 'racecar' is present in our string under test-> 'aracecard' Now, index of e is '4' in this example. if you calculate start as i - (len-1)/2 or i - len/2, there would not be any difference as len being 'odd' would lead to (len -1)/2 and (len/2) being same. lets use start = i - (len-1)/2, and end = i + (len/2) in this case. start = 4 - (6/2) , end = 4 + (7/2) start = 4-3, end = 4+3 start =1, end = 7 s.substring(1, 7+1) = 'racecar' Case-2: When palindrome substring is of 'even' length e.g. abba Lets see this case. Lets assume given string under test is-> 'eabbad' In this case, your i is going to be 2. ( This is most critical part ) With the given solution by Nick, you would found this palindrome with int len2 = expandFromMiddle(s, i, i+1) Now if you look at this method, your left which starts with 'i' is always being compared with right which starts with i+1 That would be the case here with 'eabbad'. When i is 2 ie. 'b' . Then your left will be 2 (b) and right will be 2+1 ( b) and the comparison will proceed. In this case, once you have found 'abba' then it being 'even' the index 'i' would fall in your 'first half' of the palindrome. ab | ba if you calculate start as start = i - (len/2) , it would be wrong!! because your i is not in the mid of palindrome. lets still try with this formula start = i - len/2 start = 2 - (4/2) // i =2, len = 4 ( abba) start = 2 -2 =0 ( wrong!) end = i + (len/2) end = 2 + 2 = 4 s.substring( 0, 4+1) // ''eabba' --> wrong solution!!! Here start should have been 1 lets recalculate start as- start = i - (len-1)/2 start = 2 - (4-1)/2 start = 2- 3/2 start = 2 -1 = 1 s.substring(1, 4+1) // 'abba' --> correct solution So you should calculate start as start = i - (len-1)/2 to take care of the case when palindrome is of 'even' length. For palindrome being 'odd' length it would not matter if start is calculated as i - (len/2) or i - (len-1)/2. Hope it helps!

[@AjaySingh-xd4nz]

@Garrison Shepard Glad that you found it helpful!

[@Ooftheo]

Just to clarify for those who don't understand why we do "i - (len -1)/2" and "i + (len / 2)" is because if you divide the length of the two palindromes found from string by two, you get the middle point of the length and from that, if you subtract/add the current index, you get both the starting/ending point to return the palindrome substring. Alternative would be to create a global variable to keep track of both starting and ending points and only replace them when previous length is smaller than current.

[@goodtoseeya1543]

Just wanted to say thanks

[@siddharthgupta6162]

Shouldn't we then do "i - (len)/2" and "i + (len / 2)"?

[@pratimvlogs4177]

We do "i-(len-1)/2" for only the start to handle the cases where the len is even, that is when len2 was greater than len1. In that case start is closer to i by 1 than end is closer to i

[@Vikasslytherine]

Why not just return the palindrome from the "expandFromMiddle()" function instead of returning the length of the palindrome?

[@cinderelly2224]

@@Vikasslytherine Because we're not sure if the palindrome is one like "racecar" or one like "babac." So we apply both cases to our word and return the max.

[@tindo0038]

Omg i finally found somebody who does it in java

[@Kuriocity]

yes bro all this c++ folks

[@deepaksngh9716]

It doesn't matter which language 😭😭. Meanwhile i also prefer java 🥰

[@nnasim5089]

Same here

[@chadmwest]

The -1 at line 29 is necessary because the while loop will increment left and right one additional time. For example: zovxxvo: If your final indexes are 6 and 1, you end up with 7 and 0. 7-0-1=6, which is the length of the palindrome.

[@calp8395]

Took me a while to understand this code as the way it was explained was a bit confusing. There's a few things to understand in this code: 1) start and end will track the index start and index end respectively of the longest palindrome substring 2) the method expandFromMiddle is extremely misleading. It should be expandFromIndex instead of expandFromMiddle which suggests that we should expand from the centre. 3) expandFromIndex method is called for each index using two pointers, left and right, and each time it's checking that the string is a palindrome and continues to expand. This method is called twice for every index for the two different cases of a palindrome, "aba" and "abba". 4) if (len > end - start) - start and end represents the index for the longest palindrome substring, so if the len (which is Math.max(len1, len2) is greater than the current largest palindrome substring then we want to update start and end. 5) start = i - ((len-1)/2) and end = i + (len/2) --> this is really easy understand if you understand that "i" in this case is the centre of the longest palindrome. so let's say the longest palindrome of "aba" is "aba", and i would be index 1 which is the centre of the palindrome, then follow the formula to find the index of the beginning of "aba" Hope this helps!

[@archanacreator5368]

This is the most excellent explanation for this problem. I wasted lot of time re-watching this super confusing video, but finally makes sense after reading your notes and working through on a whiteboard.

[@Ash-dt7ux]

Thanks for explaining this!

[@bossmusa9075]

THANK YOU THANK YOU THANK YOU

[@rahulbawa3969]

Thanks a ton Nick. The if condition for resetting the boundary is what I couldn't really understand from the leetcode solution but thanks for explaining that. Awesome!

[@Alison-yg6qs]

Oh...! I was waiting for this thank you Nick! :)

[@arunbhati1417]

r-l-1 because r and l reach one move extra toward left and right.

[@fasid93]

have been watching several videos on the problem. so far the only explanation that clicked into my head. Thank you.

[@danieltannor6647]

@11:16 I feel like there isn't a very good explanation as to why you're doing 'len -1' on line 13, and on line 14 there is no '-1'

[@pratimvlogs4177]

We do "i-(len-1)/2" for only the start to handle the cases where the len is even, that is when len2 was greater than len1. In that case start is closer to i by 1 than end is closer to i

[@sase1017]

Great job, Nick, thanks for taking your time to make this vid

[@harinijeyaraman8789]

Your videos are amazing man. Thanks a ton for your efforts !

[@ianchui]

great question! I've gotten this question for two interviews edit: I don't remember which companies.

[@mohammedrilwan]

which company ?

[@okey1317]

Which company??!!

[@divyanshutripathi5305]

Which Company?

[@okey1317]

which company?!!!

[@dossymzhankudaibergenov8193]

@@mohammedrilwan KFC

[@Lydia-cx6cm]

Even when gpt came out, I still rely on your video when I don't get the questions...Thank you so much!

[@eldercampanhabaltaza]

Great Explanation Indeed! Thanks =). One thing to consider for other languages is that in Java, an even number divided by 2 is rounded down. i.e. 5/2 === 2 ( not 2.5). Here is small change for Typescript on line 12* if(len > end - start) { start = i - Math.floor( (len -1) / 2 ) end = i + Math.floor(len / 2) console.log({len, i, start, end, s: s.substring(start, end +1 )}) }

[@ragibhussain5257]

A bit point to add that if we have to return the first occurence of the palindrome, if there are many with same length. Thus, in the main method , where (len > end - start), we need to add 1 (len > end - start + 1), so for an example if the palindrome length is 1 the end and start are same and thus 1 > 0 and we will keep on updating the start and end and return the last occurence but we needed to return the first occurence.

[@sukritakhauri648]

Perfect explanation, one just needs to modify the condition (len

[@linyuanyu5417]

But I don't get that start and end is always 0, why do you have to compare it with len?

[@linyuanyu5417]

And how do you ensure that end-start+1 will give you the first longest palindromic substring?

[@sathishkumar-dc9ce]

yep..he is right u have to do end-start+1 to print first occurence if there are palindromes of same length... Actually this problem happened on gfg and later after this comment only i could pass all testcases ;)

[@adithyabhat4770]

This teached me that we have to actually care about brute force rather than trying to get most efficient solution in the beginning itself. Amazing solution.

[@amitgupta3320]

Nick ,you are amazing. Thanks for sharing your idea.

[@DanielOliveira-ex6fj]

Your reasoning for the +1 was correct. The problem was that right should be right-1 and left should be left+1, as you decremented/incremented and then checked if it you still had a palindrome. That’s why -1 worked, you ended up subtracting -2.

[@ankuradhey]

Smart boy

[@ryoyamamoto6488]

I'm Japanese (meaning its hard for me to understand English sometime) and currently studying Leetcode hard, so if you have time, can you write some actual code (maybe partially)? you think he should write right --; left ++; and check if it still had a palindrome? sorry if I'm saying something really stupid.

[@ahkim93]

can you please explain why right should be right-1 and left should be left+1 in the return statement? thank you! got it! it's cause the last iteration we incremented right by 1 and decremented left by 1 to much then the while case broke.

[@waterstones6887]

I was also confused at the beginning of this point. thanks for the clear explanation

[@hoangnguyendinh1107]

@@ahkim93 because the final while loop condition that break the loop is actually the right+1 and the left -1 (you gonna return the right and left) but before that must check that the character at left-1 and right+1 are not the same. So right +1 - (left-1) -1= right - left +1 which is the actual length

[@mauricegoldberg7458]

Clearest explanation of this problem I've seen so far. Thanks!

[@saikumartadi8494]

thanks for the video .can u please make a video on the O(n) approach. Manachers algorithm

[@alinal6852]

This video is really helpful! Thanks!

[@shubhamtiwari6660]

Man what an explanation. Thanks, dude.

[@paulonteri]

This is one of you best explanations.

[@ByteMock]

great question, we will have to use this one soon.

[@crazyguy338]

12:32 and that's when I subscribed great explanations btw!

[@estherdarrey2090]

Hey Nick, could you please explain why we are initially taking start=0 and end=0 when we are supposed to take pointers from middle?

[@HimanshuSingh-dh4ds]

exactly my point... i was wondering this algo was supposed to start from middle of the string

[@natiatavtetrishvili3108]

You will have to check every element for being a possible middle element of a palindrome. You can start from the middle but still you need to check every element. In a best case scenario, where the whole string is a palindrome, you might get the answer sooner, but if the longest palindrome is not the whole input, you still need to check every element. i.e input like "aaabc" or "abccc". I hope I was clear )

[@javawithhawa]

@@natiatavtetrishvili3108 thank you, that was clear!

[@myvinbarboza3038]

everything is awesome the left> right is not required though also start=i-(len-1)/2 It is basically done for all even cases where we have a right value that's equal but not left Assume start=i-(len)/2 Take ex cbbd which will return a len of 2 when i=1 we would get an answer of cbb as our start=1-1=0 Hope it helps :)

[@shyamutty]

checked in C# and this change in line 18 was required: return s.Substring(start, end - start + 1);

[@Scratchmex]

If we invert the string and there was a palindrome in the first, it will also be in the inverted one so you can convert this problem into the Longest Common Substring one

[@chinmayswaroopsaini7890]

you save the day man. keep going

[@gauravghosh6562]

how about checking for pallindrome for the actual string first as it is the longest substring and then if it is not a pallindrome, breaking that substring by 1 character from each side until a pallindrome is left

[@spuranyarram8711]

@Nick can we use the same approach to try and solve Longest Palindromic Subsequence (LC 516) ?

[@AJITSINGH-ez1it]

can we return right-1 - (left+1) +1 for better understanding ?

[@shafidrmc]

Can anyone explain the intuition behind the -1 in right-left-1 part? I get that right - left part but I had to do some hand calculation to see the -1 part and in an interview, I wouldn't have the natural intuition to do the -1 so I wanna see the logic behind the -1. Thanks

[@Perldrummr]

Thanks man, helped me understand this solution much better.

[@chaithnay111]

Thank you for such a great explanation

[@manishankar8688]

correction : return s.Substring(start, end-start + 1); line number 18.

[@kartiksoni825]

it gives the right answer, but could you explain why is it not simply start, end(+1)?

[@shinratensei5734]

@@kartiksoni825 second parameter denotes the no of characters to be considered

[@harshagarwal3531]

thank u so much, was debugging since an hour

[@shinratensei5734]

@@harshagarwal3531 good to know...but go through stl once

[@harshagarwal3531]

@@shinratensei5734 ya sure, can you suggest any cheat sheet or tutorial in which I can see at a glance. Thank u in advance

[@c0411026]

Great video, thanks for the explanation!

[@jaylenzhang4198]

Good answer and explanation! Thanks!

[@enrro]

You're not an idiot dude. You have teach me much!

[@prajwalsolanki1049]

In the brute force solution, how can I keep a track of the longest substring? Something that can store the values of i and j (end index values of longest substring), and update it when a new maximum length is found. I can only think of a Hashmap with something like Please help me out. Thank you!

[@chodingninjas7415]

more interview questions nick

[@suashischakraborty3650]

Hi Nick just going through your videos before my exam tomorrow, Seems the way you teach us is really different from others , I am having a hard time in understanding dynamic programming, I couldn't get any of the content here and there who explains well , could you start a new playlist of dynamic programming....thanks in advance love from India ❤️

[@taekwondoman2D]

Lol this question screwed me before, thanks for the explanation.

[@anywheredoor4699]

I have a question the second call to expand method with I at the last index won't that give index out of bounds, how is the code working

[@mukeshmaniraj]

super, thanks,I am going to try and see if this algorithm works for the longest substring with at most k distinct characters question,

[@harold3802]

These videos are GOLD

[@suharajsalim4549]

Great explanation! Thank you :)

[@MAXNELSON]

If you are using JAVASCRIPT, or a dynamic language, or any language that doesn't allow type declaration, make sure you are parsing integers where required so your indices don't get messed up. IE: 0.5 = 0 as an Int, when lines 13 and 14 could be meant to produce a 1.

[@nikhilaourpally8905]

You communicate very clearly! There aren't a lot of software developers who can do that.

[@himanshukhanna2589]

Can anyone please explain why inside the if condition (len>end-start) (len-1)/2 subtracted from i for value of start but len/2 only added to i for value of end.

[@amandapanda3750]

really appreciate these videos.

[@alexcoding99]

Great video and very good explanation!

[@akhila5597]

This is the best explanation !!! Thankssssss

[@MegaSethi]

Why is there a right - left -1 at expandFromCenter method? I think it should be right - left +1, don't know why it works. can someone explain?

[@michaeldang8189]

Add a special check that if max len is same as the string length, break out. You will not find longer ones by advancing i. Though it will not change the runtime complexity.

[@andywang4189]

Good explanation, thanks!

[@RajSingh-gz6mr]

Nicely Explained!

[@skumakerguitar8708]

nick white thanks bro! i'm sick with dynamic programming haha

[@tanuj02940294]

That was a great explanation, loved it in the first go. And cherry on the cake, it's in java 😃

[@YNA64]

sorry at 11:00 why wwill the index the we are at be the center of a palindromic sub string?

[@shivangishukla2629]

amazing explanation! thanks

[@pragyapriya9049]

I/P -> ["ac"] O/p -> "a" This is 2nd testcase in leetcode. This code gives output as "c" instead of "a". However it passed the test case in leetcode. Could anyone please help what change do we need to make in this code to generate O/P as "a" instead of "c". I am stuck there. Any help is appreciated. Thanks

[@EseaGhost]

what if the input string was babed? then the expand from middle doesnt work...

[@suryaajha2142]

You explain the solution like a god

[@johnleonardo]

this explanation was god-tier, you legend.

[@user-ng9lt5db1l]

Thank you so much for good explanation

[@tigergold5990]

Here’s a slightly more complicated optimization that I used: start checking characters as the center from the middle. If you find a palindrome, adjust the loop’s boundaries so it doesn’t check the first character as the center for a palindrome of length 5, for example.

[@iamabhhilashdk]

Hi Nick. I follow your Videos to learn to solve coding problems. But I am weak at figuring out edge cases and evaluating boundary conditions and coding for them. Is it possible for you to make a video taking an example and explain how to identify edge cases and code for them.

[@mayankjain9821]

Hey, I am also a beginner in my journey to learn DSA. From my POV, solve at least 100 problems before you start thinking about patterns. This subject has a steep learning curve and you would show improvement only after considerable effort at the start.

[@mohitsoni7787]

Thanks man....Can you explain some questions regarding the image of trees.

[@cmliu22]

just couldn't understand the final step, when return substring, why need add 1 to end, someone explain plz. Like in the "abba" case, end = 1 + (4 / 2) = 3, so substring ( 0, 4) would mess up, right ?

[@harshittrehan6232]

Can someone explain the start and end indices determination ? (len-1/2) and (len/2) A little lost there. Great video tho. Clears everything up nicely.

[@Michaeljamieson10]

it is because the length of the longest palindrome needs to be split between two values(why we divided by two) then it needs to be placed on the correct index (why we subtract i in start and add it in end+1)

[@debanjanghosal618]

How is the expand method working at the middle of the strings?

[@abhishekvishwakarma9045]

Nice and easiest Explanation thanks 😎

[@arunkumarchinthapalli2005]

Will it work for "abcabcdeed". The sub string of palindrome is at the end "deed"

[@nehachaudhary4388]

In the expandFromMiddle while condition, shouldn't be right

[@sarangsowmya9854]

How about reverse the string and walk it while comparing with the original

[@ashwinishanbhogue2917]

Hey Nick, It would be great if you could do an explanation for Leetcode Problem 6. ZigZag Conversion.

[@kumararab758]

Smoothly explained. Thanks, bruh

[@sukritakhauri65]

Great Explanation

[@StewieGriffin]

time complexity if done with sliding window?

[@yumo]

Great explanation, thanks

[@sharuk3545]

Awesome Explanationnnn broo

[@mikasaackerman2694]

Nice Explanation!! Just one question.... Can anyone explain why the return statement was right-left-1 instead of right-left+1? The latter one makes more sense.

[@princepuri1188]

this is because we have to exclude the incremented left and right where the conditions of the while loop broke and we want to have the length till, the string was palidrome.

[@yogesh9193]

The but'um in your every video reminds me of himym :D ... Great explanation :)

[@suprathikm3639]

Awesome explanation.

[@harishkandikatla9791]

Please do a video on Manacher's algorithm

[@techwithwhiteboard3483]

theres already a video by a channel named ideserve watch it its worth it

[@hacker-7214]

damn these edge cases, and bounds checking are killlling me. not only i have to comeup with the algorithm i also have to wrap my mind around the bounds checking. i hate how indices start at 0 and not 1.

[@manaswitadatta]

your video + comments are better than the top voted answers in LC. Sharing it there :)

[@ponka128]

Bro, you have a bug in expandFromMiddle method. It's adding /subtracting from right/left first and then calculating the length. It should calculate the length first.

[@praneeth871]

Really a good explanation

[@yaraye5397]

nice explanation!

[@ethanwalsh6529]

Should the start and end values be rounded down? One of (len - 1)/2 and (len/2) is going to be a decimal value, right?

[@marcotagliani3385]

java automatically drops decimals for integer division. You should do explicit integer division ( // ) in a language like python

[@HuanNguyen-np9uw]

@@marcotagliani3385 thanks for your suggestion about explicit integer division ( // ). I've been wondering about it the whole day. Thank you again.

[@MrUGOTpwNEDbyme]

great stuff!

[@deepondas5001]

Great explanation

[@ArjunKalidas]

Your videos are usually good and makes a lot of sense, but this one was pretty vague and I couldn't understand how you were traversing the string from center to outward. Especially the start and end variables and also the return statement in the "expandFromMiddle" method "R - L - 1". Could you please explain that to me? Thanks Nick.

[@AjaySingh-xd4nz]

R - L - 1 explanation: e.g. racecar (length = 7. Simple math to calculate this would be R - L + 1 ( where L= 0 , R=6 )), considering start index is '0'. Now, in this example ( 'racecar' ) when loop goes into final iteration, that time we have just hit L =0, R =6 (ie. length -1) but before exiting the loop, we are also decrementing L by L - - , and incrementing R by R ++ for the final time, which will make L and R as ( L = -1, R = 7 ) Now, after exiting the loop, if you apply the same formula for length calculation as 'R - L + 1', it would return you 7 - (- 1) +1 = 9 which is wrong, but point to note is it gives you length increased by 2 units than the correct length which is 7. So the correct calculation of length would be when you adjust your R and L . to do that you would need to decrease R by 1 unit as it was increased by 1 unit before exiting the loop , and increase L by 1 unit as it was decreased by 1 unit just before exiting the loop. lets calculate the length with adjusted R and L ( R -1 ) - ( L +1 ) + 1 R -1 - L -1 + 1 R -L -2 + 1 R - L -1 ( there you go !!!!)

[@touwmer]

@@AjaySingh-xd4nz Thanks, it makes sense now.

[@ViktorKishankov]

There is more conceptual explanation, although it more verbose. When we count length of the substring from its start and end points we usually do R - L + 1. The "1" there is essentially "inclusion of the very first element" of the substring after we substracted R index (the length between 0 and R) from L index (the length between 0 and L). For example: "index 2" minus "index 0" would be "2" (which is absolute difference), but if we are talking about the substring length then we should add one extra element to get the proper length of 3 elements: [0,1,2]. This is specific of discrete counting of the indexes and lengths (which looks very reasonable if you try to draw this operation). So... back to the case about "R - L - 1". At the very last iteration inside the "expansion loop" we decreased the L and increased the R but since the loops is terminated it means that chars at these indexes are not part of the palindrome anymore, they point to non-matching chars now, so in order to get valid palindrome boundaries we need "to compensate them" by bringing them back one step: R = R - 1, L = L + 1. That's the place where " -1" coming from. But what about "+1"? Yes, that's the implicit part. Since we need to make that "inclusion of the first element" of the substring to get the length (explained in the first part above) we implicitly keep that "+1" carried from the last loop iteration before the loop termination. Hope this helps more than confuses...

[@cinderelly2224]

@@ViktorKishankov This makes so much sense, thank you!

[@ima9228]

Its because you are dumb

[@nandanimadhukar]

Great Video!

[@xuebindong4803]

Thank you man!