LeetCode 5. Longest Palindromic Substring (Algorithm Explained)
Vložit
- čas přidán 26. 11. 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 - Věda a technologie
![Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]](http://i.ytimg.com/vi/DK5OKKbF6GI/mqdefault.jpg)
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.
Oh...! I was waiting for this thank you Nick! :)
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.
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
@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
Great job, Nick, thanks for taking your time to make this vid
r-l-1 because r and l reach one move extra toward left and right.
have been watching several videos on the problem. so far the only explanation that clicked into my head. Thank you.
Your videos are amazing man. Thanks a ton for your efforts !
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!
This video is really helpful! Thanks!
Nick ,you are amazing. Thanks for sharing your idea.
what if the input string was babed? then the expand from middle doesnt work...
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.
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
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
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
Even when gpt came out, I still rely on your video when I don't get the questions...Thank you so much!
12:32 and that's when I subscribed
great explanations btw!
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!
Man what an explanation.
Thanks, dude.
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 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 )})
}
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.
This is one of you best explanations.
you save the day man. keep going
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
Clearest explanation of this problem I've seen so far. Thanks!
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 ;)
These videos are GOLD
sorry at 11:00 why wwill the index the we are at be the center of a palindromic sub string?
thanks for the video .can u please make a video on the O(n) approach. Manachers algorithm
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.
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
Nicely Explained!
Great video, thanks for the explanation!
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.
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.
You're not an idiot dude. You have teach me much!
Thanks man, helped me understand this solution much better.
Great video. Doing some leetcode practice before my interviews
Thank you for such a great explanation
really appreciate these videos.
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 ?
Will it work for "abcabcdeed". The sub string of palindrome is at the end "deed"
Great explanation! Thank you :)
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!
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?
can we return right-1 - (left+1) +1 for better understanding ?
more interview questions nick
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 :)
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.
Good answer and explanation! Thanks!
Great video and very good explanation!
great question, we will have to use this one soon.
This is the best explanation !!! Thankssssss
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.
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
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 explanation was god-tier, you legend.
Thank you so much for good explanation
You explain the solution like a god
Lol this question screwed me before, thanks for the explanation.
Awesome Explanationnnn broo
That was a great explanation, loved it in the first go. And cherry on the cake, it's in java 😃
nick white thanks bro! i'm sick with dynamic programming haha
Good explanation, thanks!
@Nick can we use the same approach to try and solve Longest Palindromic Subsequence (LC 516) ?
amazing explanation! thanks
Nice solution Nick :D
Its always the plus 1 or minus 1 that gets me everytime
Would this work for non-contiguous substrings (aka a subsequence)?
For example, "abaacccb" would return "bcccb" as the longest palindromic subsequence.
If not, how could your solution be modified to support that kind of input?
No
dumb...palindrome means contiguous string check only
@@HealedbyNature that's why I asked how the solution could be modified...
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
your video + comments are better than the top voted answers in LC. Sharing it there :)
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
Smoothly explained. Thanks, bruh
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 ❤️
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?
java automatically drops decimals for integer division. You should do explicit integer division ( // ) in a language like python
@@marcotagliani3385 thanks for your suggestion about explicit integer division ( // ). I've been wondering about it the whole day. Thank you again.
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.
checked in C# and this change in line 18 was required: return s.Substring(start, end - start + 1);
The but'um in your every video reminds me of himym :D ... Great explanation :)
Really a good explanation
Nice and easiest Explanation thanks 😎
Great Explanation
Great explanation, thanks
great stuff!
Awesome explanation.
I also want to come up with those independent creative solutions on my own instead of using brute force way or watching the solutions but it's so hard to do that. Is it because im dumb or something? How did u guys come up with great solutions?
me too so we are dumb
Great Video!
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
Please do a video on Manacher's algorithm
theres already a video by a channel named
ideserve
watch it
its worth it
Thank you man!
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
Love you!
nice 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,
why isn't the brute force time complexity n^2?