LeetCode 5. Longest Palindromic Substring (Algorithm Explained)
HTML-код
- Опубликовано: 26 ноя 2019
- 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 My Twitter - / nicholaswwhite
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 
Наука
![Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]](http://i.ytimg.com/vi/DK5OKKbF6GI/mqdefault.jpg)
![Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]](/img/tr.png)
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
thanks for your explanation, now everything makes sense
@@kickbuttowsk2i you are welcome!
Could you please provide the explanation of why start takes len-1/2 instead of len/2
@@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!
@Garrison Shepard Glad that you found it helpful!
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.
Just wanted to say thanks
Shouldn't we then do "i - (len)/2" and "i + (len / 2)"?
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
Why not just return the palindrome from the "expandFromMiddle()" function instead of returning the length of the palindrome?
@@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.
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!
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.
Thanks for explaining this!
THANK YOU THANK YOU THANK YOU
r-l-1 because r and l reach one move extra toward left and right.
Omg i finally found somebody who does it in java
yes bro all this c++ folks
It doesn't matter which language 😭😭. Meanwhile i also prefer java 🥰
Same here
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.
@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'
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
Oh...! I was waiting for this thank you Nick! :)
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!
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.
have been watching several videos on the problem. so far the only explanation that clicked into my head. Thank you.
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 )})
}
Great job, Nick, thanks for taking your time to make this vid
correction : return s.Substring(start, end-start + 1); line number 18.
it gives the right answer, but could you explain why is it not simply start, end(+1)?
@@kartiksoni825 second parameter denotes the no of characters to be considered
thank u so much, was debugging since an hour
@@harshagarwal3531 good to know...but go through stl once
@@shinratensei5734 ya sure, can you suggest any cheat sheet or tutorial in which I can see at a glance.
Thank u in advance
Perfect explanation, one just needs to modify the condition (len
But I don't get that start and end is always 0, why do you have to compare it with len?
And how do you ensure that end-start+1 will give you the first longest palindromic substring?
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 ;)
Clearest explanation of this problem I've seen so far. Thanks!
great question! I've gotten this question for two interviews
edit: I don't remember which companies.
which company ?
Which company??!!
Which Company?
which company?!!!
@@mohammedrilwan KFC
Nick ,you are amazing. Thanks for sharing your idea.
Even when gpt came out, I still rely on your video when I don't get the questions...Thank you so much!
Your videos are amazing man. Thanks a ton for your efforts !
Man what an explanation.
Thanks, dude.
This video is really helpful! Thanks!
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.
Smart boy
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.
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.
I was also confused at the beginning of this point. thanks for the clear explanation
@@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
more interview questions nick
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.
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 :)
12:32 and that's when I subscribed
great explanations btw!
This is one of you best explanations.
thanks for the video .can u please make a video on the O(n) approach. Manachers algorithm
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.
Great video. Doing some leetcode practice before my interviews
You communicate very clearly! There aren't a lot of software developers who can do that.
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.
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
great question, we will have to use this one soon.
You're not an idiot dude. You have teach me much!
Thank you for such a great explanation
you save the day man. keep going
These videos are GOLD
this explanation was god-tier, you legend.
You explain the solution like a god
Good answer and explanation! Thanks!
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.
Thanks man, helped me understand this solution much better.
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 ❤️
Lol this question screwed me before, thanks for the explanation.
Good explanation, thanks!
Great video, thanks for the explanation!
Great explanation! Thank you :)
nick white thanks bro! i'm sick with dynamic programming haha
That was a great explanation, loved it in the first go. And cherry on the cake, it's in java 😃
Nicely Explained!
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?
exactly my point... i was wondering this algo was supposed to start from middle of the string
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 )
@@natiatavtetrishvili3108 thank you, that was clear!
Please do a video on Manacher's algorithm
theres already a video by a channel named
ideserve
watch it
its worth it
Great video and very good explanation!
amazing explanation! thanks
Thank you so much for good explanation
really appreciate these videos.
@Nick can we use the same approach to try and solve Longest Palindromic Subsequence (LC 516) ?
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
This is the best explanation !!! Thankssssss
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.
your video + comments are better than the top voted answers in LC. Sharing it there :)
checked in C# and this change in line 18 was required: return s.Substring(start, end - start + 1);
Awesome Explanationnnn broo
Awesome explanation.
super, thanks,I am going to try and see if this algorithm works for the longest substring with at most k distinct characters question,
Thanks man....Can you explain some questions regarding the image of trees.
The but'um in your every video reminds me of himym :D ... Great explanation :)
Thanks for the great videos! So just to be clear - "expandFromMiddle" doesn't mean expand from middle of the string `s`, correct? We're expanding based on `i` as the middle char (or left and right indices from the middle in the case of `abba`)?
you are absolutely right
that got me confused all the time, so thank for the reaffirmation. it's expanding every index.
Nice and easiest Explanation thanks 😎
can we return right-1 - (left+1) +1 for better understanding ?
Great explanation, thanks
Smoothly explained. Thanks, bruh
Really a good explanation
Hey Nick, It would be great if you could do an explanation for Leetcode Problem 6. ZigZag Conversion.
Lets take an example of (RAR) sets suppose WE ARE checking palendrome property for character (A) which is at position A -- >1 we know that the expand function should return 3 in this case so (right -left-1 = 3). When we look at the above loop carefully we will see that currently left= -1 and right = 3 ( because that's where the condition will terminate). Let's put the values in the above equation 3 - (-1) -1 = 3 hence proved
Great Explanation
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
nice explanation!
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!
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
In the expandFromMiddle while condition, shouldn't be right
Rather than dealing with index, deal with String -> easier to understand
public String longestPalindrome(String s)
{
if (s==null || s.length() < 1 ) return "";
String returnString = s.substring(0,1);
for (int i = 0; i < s.length(); i++)
{
String s1 = getMaxLengthPalindromeAtI(s, i, i ); // with i at center
String s2 = getMaxLengthPalindromeAtI(s,i , i+1);
String temp = s1.length() > s2.length() ? s1 : s2;
if (temp.length() > returnString.length()) returnString = temp;
}
return returnString;
}
public String getMaxLengthPalindromeAtI(String s, int left, int right)
{
if (s==null || left > right) return null;
while (left >= 0 && right
Nice solution Nick :D
time limit exceeded with my own solution
this helped alot
Its always the plus 1 or minus 1 that gets me everytime
Nice explanation
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.
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 !!!!)
@@AjaySingh-xd4nz Thanks, it makes sense now.
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...
@@ViktorKishankov This makes so much sense, thank you!
Its because you are dumb
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.
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)
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.
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.
Easier way to understand the code with no track of start and end indices:
class Solution {
private String substring = "";
public String longestPalindrome(String s) {
if(s == null || s.length() < 1) return "";
for(int i = 0; i even.length() ? odd : even;
substring = max.length() > substring.length() ? max : substring;
}
return substring;
}
public String expandFromMiddle(String s, int left, int right){
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
return s.substring(left+1, right);
}
}
I like this solution! Easier to understand in my opinion.
but its complexity is higher in terms of theory as you are adding an O(N) operation of creating substring for every expand from middle call
Nice work bro🔥
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.
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.
Great explanation
Great Video!
sorry at 11:00 why wwill the index the we are at be the center of a palindromic sub string?
great stuff!
Thank you man!
for Input: "abcdefg" this returns "g", expected is "a" result is 'accepted'. Great video btw.
if the lengths are equal it doesn't matter what you return
i think its GFG one