LeetCode 5. Longest Palindromic Substring (Algorithm Explained)

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[AjaySingh-xdnz]

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

[arunbhati]

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

[danieltannor]

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

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

[tindo]

Omg i finally found somebody who does it in java

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

[calp]

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!

[estherdarrey]

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?

[manishankar]

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

[Lydia-cxcm]

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

[ianchui]

great question! I've gotten this question for two interviews

edit: I don't remember which companies.

[DanielOliveira-exfj]

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.

[sukritakhauri]

Perfect explanation, one just needs to modify the condition (len<end-start+1), if he wants to get the first longest palindromic substring because might be there would be more substrings of the same length.

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

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

[myvinbarboza]

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

[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

[ragibhussain]

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.

[gauravghosh]

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