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
@@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!
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.
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.
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 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.
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.
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
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!
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 ;)
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.
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.
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 )
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.
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.
@@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 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 )}) }
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 :)
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
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
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.
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!
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.
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 ❤️
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
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`)?
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.
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
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.
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 !!!!)
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...
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
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.
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?
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)
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.
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 ?
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.
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
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.
Hey Nick, I recently found out about your channel and even though this question is unrelated to the video, I was wondering if you could offer some sort of mentoring to me. I’m currently a CS student applying to internships.
Can anybody explain to me a small doubt : in expandfrommiddle function the parameter shouled be like this expandFromMiddle( s , i , i+1); expandFromMiddle( s , i , i+2); please explain !!!!
No. Ones in solution are right. as i'th pointer should either be same (e.g. "aba" : i = 1) or they should at max only differ by one position (e.g. "abba" : i = 1) And i+2 simply fails on both of such cases.
Thanks for the video. My kind Suggestion:First 5 min can be spent on explaining Logic on a paper or any software and then instead of typing the code,Just walk us through the code.Thank you
you said in starting that O(n^2) time for generating all the sub strings possible and checking takes linear time so you said O(n^3) but if we store the combinations and check if palindrome or not then it is O(n^2) time complexity
I don't think this works. Consider the string "aaaab123baaaa". "aaaab" is present in both the original and the reversed, but is not a palindrome. If you only look at matches between substrings at the same indices, it also doesn't work. Consider "ab" -- the longest palindrome is "a" or "b", but the longest shared substring at matching indices is "".
Hi Nick . I tried running this code and made the necessary changes for C# but I am still getting an error. Also I had a doubt about i=0. left=-1 and right would be 1. we will return 3 as Length. Thanks in advance
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!
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
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.
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
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
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!
Oh...! I was waiting for this thank you Nick! :)
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 ;)
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
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.
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.
have been watching several videos on the problem. so far the only explanation that clicked into my head. Thank you.
thanks for the video .can u please make a video on the O(n) approach. Manachers algorithm
Great job, Nick, thanks for taking your time to make this vid
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!
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 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 )})
}
Your videos are amazing man. Thanks a ton for your efforts !
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 :)
@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
Even when gpt came out, I still rely on your video when I don't get the questions...Thank you so much!
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
Nick ,you are amazing. Thanks for sharing your idea.
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
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
more interview questions nick
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.
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!
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.
Man what an explanation.
Thanks, dude.
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 ❤️
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
Clearest explanation of this problem I've seen so far. Thanks!
can we return right-1 - (left+1) +1 for better understanding ?
checked in C# and this change in line 18 was required: return s.Substring(start, end - start + 1);
great question, we will have to use this one soon.
Great video. Doing some leetcode practice before my interviews
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.
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?
super, thanks,I am going to try and see if this algorithm works for the longest substring with at most k distinct characters question,
This video is really helpful! Thanks!
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.
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
Lol this question screwed me before, thanks for the explanation.
This is one of you best explanations.
12:32 and that's when I subscribed
great explanations btw!
nick white thanks bro! i'm sick with dynamic programming haha
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.
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
Thanks man....Can you explain some questions regarding the image of trees.
sorry at 11:00 why wwill the index the we are at be the center of a palindromic sub string?
You're not an idiot dude. You have teach me much!
Hey Nick, It would be great if you could do an explanation for Leetcode Problem 6. ZigZag Conversion.
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
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.
Thank you for such a great explanation
In the expandFromMiddle while condition, shouldn't be right
You communicate very clearly! There aren't a lot of software developers who can do that.
That was a great explanation, loved it in the first go. And cherry on the cake, it's in java 😃
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...
Thanks man, helped me understand this solution much better.
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)
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.
Good answer and explanation! Thanks!
Please do a video on Manacher's algorithm
theres already a video by a channel named
ideserve
watch it
its worth it
Will it work for "abcabcdeed". The sub string of palindrome is at the end "deed"
You explain the solution like a god
you save the day man. keep going
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 ?
The but'um in your every video reminds me of himym :D ... Great explanation :)
this explanation was god-tier, you legend.
Great video, thanks for the explanation!
what if the input string was babed? then the expand from middle doesnt work...
Great video and very good explanation!
These videos are GOLD
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.
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
Is it more optimal to call the method twice for both cases vs checking if the length is even or odd to know which case to handle?
It's a substring. There'll be no definite length as you don't know what you're looking for until you find it
Great explanation! Thank you :)
How about reverse the string and walk it while comparing with the original
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.
Good explanation, thanks!
your video + comments are better than the top voted answers in LC. Sharing it there :)
Hey Nick, I recently found out about your channel and even though this question is unrelated to the video, I was wondering if you could offer some sort of mentoring to me. I’m currently a CS student applying to internships.
join discord and message me
time complexity if done with sliding window?
Can anybody explain to me a small doubt :
in expandfrommiddle function the parameter shouled be like this
expandFromMiddle( s , i , i+1);
expandFromMiddle( s , i , i+2);
please explain !!!!
No. Ones in solution are right.
as i'th pointer should either be same (e.g. "aba" : i = 1)
or
they should at max only differ by one position (e.g. "abba" : i = 1)
And i+2 simply fails on both of such cases.
Thanks for the video. My kind Suggestion:First 5 min can be spent on explaining Logic on a paper or any software and then instead of typing the code,Just walk us through the code.Thank you
I think it'll be better if he doesn't change his style. It's perfect for everyone.
@@shubhamtiwari6660 yes this is perfect
you said in starting that O(n^2) time for generating all the sub strings possible and checking takes linear time so you said O(n^3) but if we store the combinations and check if palindrome or not then it is O(n^2) time complexity
Yes, you are right. But now you're incurring extra space on the order of O(n^2) so you have to consider if the tradeoff is actually worth it.
it would be great if you can add the leetcode question link :)
how about reverse the string and the longest substring between the original one and the reversed one -> O(n²), but the optimal solution is O(n)
I don't think this works. Consider the string "aaaab123baaaa". "aaaab" is present in both the original and the reversed, but is not a palindrome. If you only look at matches between substrings at the same indices, it also doesn't work. Consider "ab" -- the longest palindrome is "a" or "b", but the longest shared substring at matching indices is "".
What if you have string “fsdfbaab” I don’t see how your solution would still work
it works brother
How much time do you guys struggle with a problem until you give in and look at the solution?
amazing explanation! thanks
Hi Nick . I tried running this code and made the necessary changes for C# but I am still getting an error. Also I had a doubt about i=0. left=-1 and right would be 1. we will return 3 as Length. Thanks in advance
Put parentheses around left + 1 part. That fixed it for me.
You have explained nicely but you should show by example of a word at each step...& That's becoming a bit difficult to get.....
really appreciate these videos.