Thanks a lot! Your tutorial is the best of all. The four cases were so clear and concise. After many struggles with the other written tutorials, I was finally able to implement the method by looking at the cases provided by you!
Thank you for the video. The explanation was quite lucid. One suggested correction though, at 14:20, I suppose you would want to put the value '9' against the 13th element i.e. 'x' and not against the 14th element i.e. 'a'. Thanks again!
you messed up in explanation where you started to explain how to choose next center may be around 3:00 . without explaining logic fully ..... you kept moving ... lost you there
This is where I got lost too. The math clarified it when I worked it out. Since the "a" at index 4 will have the same possible palindrome length around it as the one at index 2, and since the max palindrome length of that character is 1, 4+1 does not take you outside the bounds of the longest palindrome we have since encountered, ie 5 < 6. But, the "b" at index 5 is like the "b" at index 1, in that it has a longest palindrome around it of length 3. Since 4 + 3 takes us outside the upper bound of the longest palindrome, whose upper bound index is 6. So, since 7 > 6, it's a candidate. This is what he means when he says "b" at index 5 might possibly expand outside the bounds of the longest palindrome we've encountered so far.
I think the confusion is mainly because of the ""expansion for every element". That's why it kinda looks like it's O(n²). I scratched my head the whole day and finally understood how it's O(n). If you try to manually run this code( medium.com/hackernoon/manachers-algorithm-explained-longest-palindromic-substring-22cb27a5e96f ) on paper with some examples, you will find out that once the palindrome is calculated up to 'r', no other element enters the "while loop" again. Because the 'mirror' has already calculated the palindrome for that element. It will enter the "while loop" again when either the element is after 'r' or when the element's mirror's palindrome exceeds 'r'. I know what I am saying might sound like gibberish but once you have tried to run this algorithm in a '7-8' length word example, you will see I am trying to say.
Can u give a better explanation as to why this algorithm runs in linear time? The algorithm goes several times back and forth on the tape... Run time complexity is not as straightforward as u mentioned.
+Emma Bostian - How can you say that ? For every palindrome centre , he seems to be checking to the left and right ( this could be a max of n-1 also... ). Can you say how it is O(7n) and not O(n^2).
but this algorithm doesn't expand from the center at any index right? It skips a lot. And also for calc the new length at a specific index, it takes use of the old data instead of calc from scratch. There must be a strict math way to prove the time complexity, it is not easy to see.
5 should be replaced with 9, since we are finding with respect to x. When we reached at point x we had >=5 situation, then again look with respect to x we get 9.
There's something I didn't understand which is preventing me from seeing why its O(n) time complexity. Specifically how you are checking the max size of the palindrome around each center. At each new iteration you are still checking the same positions. For example, pos 0, 1, 2, 3. Based on your explanation you are reiterating through those first positions multiple times, you aren't visiting them only once. When you reach pos 3, you're going back through 0-2 again to check. I thought this would only be one iteration through but you're revisiting the old positions again. The only time you aren't revisiting is when you use your largest palindrome as a mirror. This seems like its not really linear. It is in that its 0(n) but not in the literal sense of linear since you are constantly revisiting previously visited positions.
Let S be the string and LP[i] be the longest palindrome centered at index i of S. LP[i] = L implies that all(S[i-j] == S[i+j] for j in range(L//2 + 1)). As an example, the fact that LP[3] = 7 implies S[0] = S[6] S[1] = S[5] S[2] = S[4] S[3] = S[3] This leads to a question at 5:05, LP[4] >= 1 (the longest palindrome centered around S[4] is greater than or equal 1), but it also can't be >1 right? Assume, LP[4] > 1. If LP[4] > 1, then LP[4] must be at least 3 implying that S[3] and S[5] must be equal. However, noting that S[1] = S[5] due to LP[3] = 7, then S[1] = S[3] = S[5], but this implies that PL[2] >= 3 which is a contradiction given we know that LP[2] = 1. Therefore, LP[4] must equal 1.
I am unable to follow you starting from 8:10 where you said that x at position 7 can't be further expand because position 10 is different from position 0 thus cannot be a 'a'. But at this point we should look at position 4 and check "if position 10 == position 4" and it seems to me position 4 is 'a' by accident. if I change you string to "cbaxabaxaba", this analysis doesn't hold.
Very good question, in your example "c b a x a b a x a b a" - With b (position 5) as center we get 9 as palindrome, and when moving to x (position 7), the mirror (position 3 which is also x) will be within the range of left edge (exactly at left edge index which is 1). This will fall under the 3rd category (3. Palindrome expands till right edge and the mirror palindrome is still in the range - please watch full video) and x will become new center and will be palindrome 9.
Hi Tushar, at 13:33, we have found the palindrome of length 11 at position centering at position > (N/2) where N is the length of the string. Can we stop at a palindrome length > N/2 and at a centering position >= stringLength/2, since the next 2 chars would be contained in the current large palindrome. Or can we in short ensure in this example that we do not process after palindrome length 11 is found, or could there be a corner case there ?
Not really will be true for all cases - consider "c b a x a b a x a b a x a", the palindrome at b (position 6) will be 9. the Value 9 > N / 2 (N=14). But at position 8 with x as center, the palindrome value is 11 (if we break, we'll miss this condition). Even for best cases, if the characters included in the larger palindrome then we could simply substitute the mirror values, which is just assignment and can be in o(N).
@@paramagurug9237 the case above that you shared has the b(position 6) towards the left side (and not past the halfway point) as the total length of the string is 13 so jumana's suggestion still holds. We can restate the above condition in the following manner instead - when the (number of chars towards the right of the next possible center < half of the maximum palindrome string found till now) we can say that the current maxima will be the global maxima even after those chars are processed.
I have got a ques. At time 6:00 in the video, We got max palidrome length as 9 at index 5; going any further can't give us any palidrome greater than this. I think we can stop there. This can be a optimization done in above algo. Tushar, let me know if I am wrong.
It is difficult to do this optimization, there are chances with best cases it will be helpful. Consider the same example with little modification - "c b a x a b a x a b a x a" with b as center (position 6) the palindrome is 9, but when you move to position 8 (x as center) then the palindrome will be 11.
I kind of wish he had put in the math for how we determine the four cases: as discussed we just "looked" at the expansions centered on the new possible Ith value and determined it visually expanded over the boundaries of the current max palindrome. Case 4 specifically is if there is a prefix of (curr_len-1)/2, then the new center is (curr_len/2)+(prefix_len/2) right?
what if i placed y at index 5 in array at 8:36,current array will remain of same size but palindrome around x(index 7) will go beyond current array.It will contradict what u say ,can u explain plz?
at 4:47 when you say this isde should be a mirror of this side thats when the algorithm just clicked !!! thank you very much , reading on geeksforgeeks did allow me to understand it so easily
This video is very helpful for me, while still, I need make 2 points clear by myself. 1. Why array[7] can't be the new center in 8m18s 2. Why the time complex is O(n)
Amazing explanation, very clear. People who are complaining about not understanding... I don't know, its not that complicated, just watch it again a few more times? Its really not that hard to grasp.
Hello Tushar, I wanted to point out a small issue, which I am not sure if it is my implementation issue or some bug related to your algorithm but this algorithms seems to exceed time limits when we give a string with only a's having a length of 10^5
Bro its not O(N) even for odd case.. i feel . Can you pls answer this.. because going though particular index again we to expand for palindrome. What about that?.. then for even complexity will increase
At 12:22 you are saying that x should not be the centre. Based on my understanding "should not be centre" means we should not spend time in calculating the longest palindrome But you wrote 5 in front of x. How we could write 5 without computing ? I would really appreciate your help
As per video, this condition falls under 4th point, where the mirror palindrome goes beyond the current left edge. So, at this point we have to take the minimum of (mirror value and 2* (Right edge index - current index) + 1). In this case the value will be 5 - Min (7, 2* (9 - 7) + 1). If you look into the code : line no. 98 handles this (where "end" is right edge index, j = current index and i is the center). T[j] = Math.min(T[i - (j - i)], 2 * (end - j) + 1);
Very good explanation! In 11:02, could you please explain using what case you picked 'X' as center of the new palindrome? Also could you do videos on 1D and 2D peak finding?
In the example : a b a x a b a - first a (no palindrome therefore 1), then b is the center (with "a b a" as palindrome), then a (is the right edge of the current center b, so it's not the new center), next is x (which goes beyond the right edge of the current palindrome, therefore choose x as the new center with value 7).
Generally your videos are good but I could not understand the explanation for this one. It will be great if you can create another video for Manacher's.
Does finding the palindrome around each index not increase the time complexity? If this were so, why wouldn't the naive method have the same complexity?
hello tushar, I have question about subarray sum II, the problem is Given an integer array, find a subarray where the sum of numbers is between two given interval. Your code should return the number of possible answer. for example: Given [1,2,3,4] and interval = [1,3], return 4, because The possible answers are: [0, 0][0, 1][1, 1][2, 2], O(n ^ 2) method is easy to implemented, but how to solve that in O(nlogn) time? My teacher said I can calculate the prefix sum array, then sort the that array, then I can get the answer, it is unreasonable.
hello you videos are great please can you please solve this one: define an algorithm to find longest balanced sub-string of a certain string of packets and parenthesis
At 3.21, at index 6. 'a' expands and is a candidate for center? No palindrome can be formed with characters to either side of 'a' at index 6. Can you clarify? Looks like you aren't answering any questions people have asked you below in comments.
question : You directly said, "center is expanding this much" ,how is expansion measured? (eg: a[3] = 7) 2. Shouldnt we stop moving mid if END_ARRAY - mid < max(CENTRAL_ARRAY) /2. Doesnt make sense to keep moving on the mid
How do u calculate the palindrome length.your getting one for the first character when it should be zero ,because it has no further left but right.Explain ourself.
+Tushar Roy I am unable to follow the video around 6:30 mins, when we chose value of 5 when comparing with 7. Still stumbling on that point. And also wondering if its O(n) since we are still scanning for lot of centers. Any tips would be appreciated.
+Tushar Roy why: (2 * (end - j) + 1) in the condition, is it always true that its a pallindrome with everything between j and end ? T[j] = Math.min(T[i - (j - i)], 2 * (end - j) + 1);
Nevermind, Got it !! Thanks for the tutorial. Also , If we change (2 * (end - j) +1) to (2 * begin - (i - (j - i))) +1 it is more intuitive articles.leetcode.com/wp-content/uploads/2011/11/palindrome_table5.png
I was going through the code in github: Although there's a comment added
//Mark newCenter to be either end or end + 1 depending on if we dealing with even or old number input int newCenter = end + (i%2 ==0 ? 1 : 0); with this code you are not taking $ to be the next center node, why?
When I asked why I was rejected from the entry level position at Panasonic for 60k a year full time I was told it was because I did not come up with an O(n) time complexity for this problem. I was given 1 hour.
very good initiative to explain these concepts to us ... i always liked ur videos especially on BIT ... If possible post videos on suffix array + Lcp by o(n) (without suffix trees) ... just goes over my head ... thanks
there is no reason to continue when 'x' at position 7 has palindrome of length 5, which is less than the 9 found so far, so your explaination since 7:30 makes no sense to me, also since 'y' at position 10 in the 2nd case has palindrome of length 11, there is no need to continue since 13:40 because you cannot find a palindrome which length is larger than 11
Normally your videos are very clear but this wasn't one of them.
The algorithm was a bit complex, he did his best, i am sure!
Yes
me too, lol
At first I thought this is not clear but as I went through videos by others I found this one the best.
subtitles: hello friends my name is too sharp 😂😂😂
My name is Not Sure
Thanks a lot! Your tutorial is the best of all. The four cases were so clear and concise. After many struggles with the other written tutorials, I was finally able to implement the method by looking at the cases provided by you!
Way better than all written tutorials for manachers!!! this was amazing
At 14:20 i feel there should not be 5 followed then 9, 5 should be replaced by 9. Since at end we are finding palindrome around x not a.
And the Oscar goes to Tushar Roy XD
As always, concise, accurate, and easy to understand explanation of a rather tricky algorithm.
LOL cOnCiSe
Thank you for the video. The explanation was quite lucid.
One suggested correction though, at 14:20, I suppose you would want to put the value '9' against the 13th element i.e. 'x' and not against the 14th element i.e. 'a'. Thanks again!
wow, it was so hard to explain yet you did. Thanks
you messed up in explanation where you started to explain how to choose next center may be around 3:00 . without explaining logic fully ..... you kept moving ... lost you there
This is where I got lost too. The math clarified it when I worked it out. Since the "a" at index 4 will have the same possible palindrome length around it as the one at index 2, and since the max palindrome length of that character is 1, 4+1 does not take you outside the bounds of the longest palindrome we have since encountered, ie 5 < 6. But, the "b" at index 5 is like the "b" at index 1, in that it has a longest palindrome around it of length 3. Since 4 + 3 takes us outside the upper bound of the longest palindrome, whose upper bound index is 6. So, since 7 > 6, it's a candidate. This is what he means when he says "b" at index 5 might possibly expand outside the bounds of the longest palindrome we've encountered so far.
The explanation was great. Appending '$' in between every character to make it an odd length string was an interesting idea to reduce the code.
Why is the runtime complexity O(n)? Could you elaborate more on that topic?
I think the confusion is mainly because of the ""expansion for every element". That's why it kinda looks like it's O(n²).
I scratched my head the whole day and finally understood how it's O(n).
If you try to manually run this code( medium.com/hackernoon/manachers-algorithm-explained-longest-palindromic-substring-22cb27a5e96f ) on paper with some examples, you will find out that once the palindrome is calculated up to 'r', no other element enters the "while loop" again. Because the 'mirror' has already calculated the palindrome for that element.
It will enter the "while loop" again when either the element is after 'r' or when the element's mirror's palindrome exceeds 'r'.
I know what I am saying might sound like gibberish but once you have tried to run this algorithm in a '7-8' length word example, you will see I am trying to say.
since when is "abb" a palindromic substring?? what am i missing here? ... 0:21
He obviously meant to select 'bb'. Small error.
Best tutorial on this algorithm! Very well explained and with examples!! Thank you!
Can u give a better explanation as to why this algorithm runs in linear time?
The algorithm goes several times back and forth on the tape... Run time complexity is not as straightforward as u mentioned.
+Emma Bostian -
How can you say that ? For every palindrome centre , he seems to be checking to the left and right ( this could be a max of n-1 also... ).
Can you say how it is O(7n) and not O(n^2).
but this algorithm doesn't expand from the center at any index right? It skips a lot. And also for calc the new length at a specific index, it takes use of the old data instead of calc from scratch. There must be a strict math way to prove the time complexity, it is not easy to see.
@@EmmaBostian what if you run it n times? O(nn) = O(n) or O(n^2)
@@shreyas6589 The right edge will never exceed the length of the string. So the inner loop will only run at most n times.
This video really helped me in understanding this algorithm... Keep up the good work!
The clearest explanation of Manacher's algorithm I've ever seen!!! Thanks a lot!!!
At 14:28, I think you want to put 9 corresponding to 'x' rather than 'a'.
Thanks for the video. very well explained !
Thanks! Super clear. I finally understand Manacher's algorithm.
Tushar you have explained Manacher's better than anyone !
Thanks Tushar, another great video.
question though - on 14:27 you wrote "9" in index 14 instead of in index 13. am i missing something here ?
5 should be replaced with 9, since we are finding with respect to x.
When we reached at point x we had >=5 situation, then again look with respect to x we get 9.
A very tough concept explained better than most other people out there! A great effort. Thank you for this video.
your videos are amazing. keep up the good work.
There's something I didn't understand which is preventing me from seeing why its O(n) time complexity. Specifically how you are checking the max size of the palindrome around each center. At each new iteration you are still checking the same positions. For example, pos 0, 1, 2, 3. Based on your explanation you are reiterating through those first positions multiple times, you aren't visiting them only once. When you reach pos 3, you're going back through 0-2 again to check. I thought this would only be one iteration through but you're revisiting the old positions again. The only time you aren't revisiting is when you use your largest palindrome as a mirror. This seems like its not really linear. It is in that its 0(n) but not in the literal sense of linear since you are constantly revisiting previously visited positions.
Let S be the string and LP[i] be the longest palindrome centered at index i of S.
LP[i] = L implies that all(S[i-j] == S[i+j] for j in range(L//2 + 1)). As an example, the fact that LP[3] = 7 implies
S[0] = S[6]
S[1] = S[5]
S[2] = S[4]
S[3] = S[3]
This leads to a question at 5:05, LP[4] >= 1 (the longest palindrome centered around S[4] is greater than or equal 1), but it also can't be >1 right?
Assume, LP[4] > 1. If LP[4] > 1, then LP[4] must be at least 3 implying that S[3] and S[5] must be equal. However, noting that S[1] = S[5] due to LP[3] = 7, then S[1] = S[3] = S[5], but this implies that PL[2] >= 3 which is a contradiction given we know that LP[2] = 1. Therefore, LP[4] must equal 1.
its really though ...but i belived in tushar and watched twice and now i get it ...thanks man
I am unable to follow you starting from 8:10 where you said that x at position 7 can't be further expand because position 10 is different from position 0 thus cannot be a 'a'. But at this point we should look at position 4 and check "if position 10 == position 4" and it seems to me position 4 is 'a' by accident. if I change you string to "cbaxabaxaba", this analysis doesn't hold.
Very good question, in your example "c b a x a b a x a b a" - With b (position 5) as center we get 9 as palindrome, and when moving to x (position 7), the mirror (position 3 which is also x) will be within the range of left edge (exactly at left edge index which is 1). This will fall under the 3rd category (3. Palindrome expands till right edge and the mirror palindrome is still in the range - please watch full video) and x will become new center and will be palindrome 9.
Thanks for the video!
Just a heads up, at 14:32 you marked the wrong cell. Marked cell 14 with 9, but should have overwritten cell 13's 5 with 9.
Why is it O(2n) ? at 14:53
thanks Tushar saved my hours on hanging out the same explainatory stuff on the web
this was clearly the only video till now that totally messed up!!!
Explaination was very clear and i understood this in the first watch itself. Thanks Tushar.
pLEASE be more clear in your explanations:-(
*explanation ma'am!
@@sacchitjaiswal7896 chutiye sale
@@sandeepvulluri8887 wrong! *explanations
Hi Tushar, at 13:33, we have found the palindrome of length 11 at position centering at position > (N/2) where N is the length of the string. Can we stop at a palindrome length > N/2 and at a centering position >= stringLength/2, since the next 2 chars would be contained in the current large palindrome. Or can we in short ensure in this example that we do not process after palindrome length 11 is found, or could there be a corner case there ?
Good question! I guess u r correct. there is no point in proceeding further to N/2, if you are palindrome length is already >= N/2.
Not really will be true for all cases - consider "c b a x a b a x a b a x a", the palindrome at b (position 6) will be 9. the Value 9 > N / 2 (N=14). But at position 8 with x as center, the palindrome value is 11 (if we break, we'll miss this condition). Even for best cases, if the characters included in the larger palindrome then we could simply substitute the mirror values, which is just assignment and can be in o(N).
@@paramagurug9237 the case above that you shared has the b(position 6) towards the left side (and not past the halfway point) as the total length of the string is 13 so jumana's suggestion still holds.
We can restate the above condition in the following manner instead - when the
(number of chars towards the right of the next possible center < half of the maximum palindrome string found till now)
we can say that the current maxima will be the global maxima even after those chars are processed.
from kmp to this i love this guy
finally understood this complex algo, but not completely its time complexity .
read some webpages but can't understand. your video really help
Thank You Tushar Sir for great Explanation
I have got a ques. At time 6:00 in the video, We got max palidrome length as 9 at index 5; going any further can't give us any palidrome greater than this. I think we can stop there. This can be a optimization done in above algo. Tushar, let me know if I am wrong.
It is difficult to do this optimization, there are chances with best cases it will be helpful. Consider the same example with little modification - "c b a x a b a x a b a x a" with b as center (position 6) the palindrome is 9, but when you move to position 8 (x as center) then the palindrome will be 11.
I kind of wish he had put in the math for how we determine the four cases: as discussed we just "looked" at the expansions centered on the new possible Ith value and determined it visually expanded over the boundaries of the current max palindrome. Case 4 specifically is if there is a prefix of (curr_len-1)/2, then the new center is (curr_len/2)+(prefix_len/2) right?
what if i placed y at index 5 in array at 8:36,current array will remain of same size but palindrome around x(index 7) will go beyond current array.It will contradict what u say ,can u explain plz?
Incredible explanation... WOW!!!!
Just wondering when do you start to ask the question what could be my next center?
0:22 - how cells 8,9,10 (a,b,b) is a palindrome?
Bhool ho jati hai yun taish mein aya na karo, let's be human alright!
at 4:47 when you say this isde should be a mirror of this side thats when the algorithm just clicked !!! thank you very much , reading on geeksforgeeks did allow me to understand it so easily
Thanks a lot Tushar sir !!!
This video is very helpful for me, while still, I need make 2 points clear by myself.
1. Why array[7] can't be the new center in 8m18s
2. Why the time complex is O(n)
how was 0:23 palindromic?? xD
"aba x aba" how was it not palindromic ?? xD
Amazing explanation, very clear. People who are complaining about not understanding... I don't know, its not that complicated, just watch it again a few more times? Its really not that hard to grasp.
Guess you were not prepared to present this algorithm
Subtitles : hello my name is too sharp 😊
Thanx Tushar made my life easy bro...
Why do you mark 3 last letters as a palindromic substring whereas they're not abb. At the 23d second of the video
Hello Tushar,
I wanted to point out a small issue, which I am not sure if it is my implementation issue or some bug related to your algorithm but this algorithms seems to exceed time limits when we give a string with only a's having a length of 10^5
How abb is palindromic ?
Please correct if I am wrong.It's from index 8 to 10.
you explained it perfectly
Nice explaination Tushar :)
u made it easy
NICE I don't know why people dislike your video
Bro its not O(N) even for odd case.. i feel . Can you pls answer this.. because going though particular index again we to expand for palindrome. What about that?.. then for even complexity will increase
I understood everything. /s
Very nicely explained. Thanks! It would've been even better if you could put up some code as well.
The last string was supposed to be even length, but it was odd length
palindromic string of even length *, it is correct
Would it not be 1st=1 central 'a' [a], 2nd=3 central 'b' [a,b,a], 3rd=5 central 'a' [a,b,a,b,a]?? It seems you have many errors in your explanation.
nice explanation...especially the 4 cases for centre selection
Good explanation, Tushar. But when you have sample with red marker, you need to put last 9 in place of 5.
At 12:22 you are saying that x should not be the centre. Based on my understanding "should not be centre" means we should not spend time in calculating the longest palindrome But you wrote 5 in front of x. How we could write 5 without computing ?
I would really appreciate your help
As per video, this condition falls under 4th point, where the mirror palindrome goes beyond the current left edge. So, at this point we have to take the minimum of (mirror value and 2* (Right edge index - current index) + 1). In this case the value will be 5 - Min (7, 2* (9 - 7) + 1).
If you look into the code : line no. 98 handles this (where "end" is right edge index, j = current index and i is the center).
T[j] = Math.min(T[i - (j - i)], 2 * (end - j) + 1);
can you explain this part clearly?
In second case the at 13th index it should be 9 no?? But did you took 5? Only this point i didn't get. Will you please enlighten?
11:01 didn't understand exactly why at this point we pick a new centre, can somebody please explain the reasoning?
Very good explanation!
In 11:02, could you please explain using what case you picked 'X' as center of the new palindrome?
Also could you do videos on 1D and 2D peak finding?
In the example : a b a x a b a - first a (no palindrome therefore 1), then b is the center (with "a b a" as palindrome), then a (is the right edge of the current center b, so it's not the new center), next is x (which goes beyond the right edge of the current palindrome, therefore choose x as the new center with value 7).
In your code you set the new center according to i is even or odd ? why
Generally your videos are good but I could not understand the explanation for this one. It will be great if you can create another video for Manacher's.
Does finding the palindrome around each index not increase the time complexity? If this were so, why wouldn't the naive method have the same complexity?
really appreciate how you make logics so easily understandable
hello tushar, I have question about subarray sum II, the problem is Given an integer array, find a subarray where the sum of numbers is between two given interval. Your code should return the number of possible answer. for example: Given [1,2,3,4] and interval = [1,3], return 4, because The possible answers are: [0, 0][0, 1][1, 1][2, 2], O(n ^ 2) method is easy to implemented, but how to solve that in O(nlogn) time? My teacher said I can calculate the prefix sum array, then sort the that array, then I can get the answer, it is unreasonable.
your videos are always clear, but not this one. This is your video of 5 years ago. Why don't you make the video on this algorithm again?
How does it make it O(n)? Very act of finding a palindrome on either side of an index you are potentially going n indices. What am I missing?
Each palindromic checks has an O(1) time complexity, so the total complexity is O(n).
I am confused about 1st point and 3rd point looks like same thing
Would you consider this algorithim to be following the concept "dynamic programming"?
I feel like this is more similar to sliding window tbh
Generally your videos are too good expect this.
except*
why at the position of 'b' we need to find NEXT CENTER ?? i just cant understand plz help me
hello you videos are great
please can you please solve this one:
define an algorithm to find longest balanced sub-string of a certain string of packets and parenthesis
At 14:30 you are supposed to replace 5 with 9.
Nice work ! Thank you !
can I do it just using a stack? start from the left pushing and popping when I need, I think it could be done in O(n)
Ok! Now I got it :) Thanks Tushar
A lengthy algo!! man i keep forgetting this
imp algorithm
Man, you are so fast.. the four rules you have written on board, you could have made it in less speed to understand the concept. Thanks for the video!
At 3.21, at index 6. 'a' expands and is a candidate for center? No palindrome can be formed with characters to either side of 'a' at index 6. Can you clarify? Looks like you aren't answering any questions people have asked you below in comments.
great explanation!
Its a nice video. I just wanted to ask you, that for any String(Odd/Even) we need to append "$" (2*n+1) ??? Or anything better suggestion u have ?
question : You directly said, "center is expanding this much" ,how is expansion measured? (eg: a[3] = 7)
2. Shouldnt we stop moving mid if END_ARRAY - mid < max(CENTRAL_ARRAY) /2. Doesnt make sense to keep moving on the mid
How do u calculate the palindrome length.your getting one for the first character when it should be zero ,because it has no further left but right.Explain
ourself.
+Tushar Roy I am unable to follow the video around 6:30 mins, when we chose value of 5 when comparing with 7. Still stumbling on that point. And also wondering if its O(n) since we are still scanning for lot of centers. Any tips would be appreciated.
+Tushar Roy why: (2 * (end - j) + 1) in the condition, is it always true that its a pallindrome with everything between j and end ?
T[j] = Math.min(T[i - (j - i)], 2 * (end - j) + 1);
Nevermind, Got it !!
Thanks for the tutorial.
Also , If we change (2 * (end - j) +1) to (2 * begin - (i - (j - i))) +1 it is more intuitive
articles.leetcode.com/wp-content/uploads/2011/11/palindrome_table5.png
can you explain this part???
I was going through the code in github:
Although there's a comment added
//Mark newCenter to be either end or end + 1 depending on if we dealing with even or old number input
int newCenter = end + (i%2 ==0 ? 1 : 0);
with this code you are not taking $ to be the next center node, why?
*That what happens when you memorize algos* LMFAO!!!
U mean tushar sir memorize them? ?
Agreed, where can I find the explanation. Any resources would you like to share
@@faizanurrahman6046 just search with the problem name.. you will find many youtubers
When I asked why I was rejected from the entry level position at Panasonic for 60k a year full time I was told it was because I did not come up with an O(n) time complexity for this problem. I was given 1 hour.
Thanks Tushar for such an awesome video !!
I just have a query. why we need to preprocess the array in case there are even lenghted panlindromes?
Because this algorithm is all about expanding from a center character, and even length palindromes do not have a center character.
may I know at which point we need to pick a centre and start back ward calculation
that is the biggest coconut i have ever seen . looks like Indian sounds like Irish. well jokes aside the video was nice. i liked it. gambareyo!!
very good initiative to explain these concepts to us ... i always liked ur videos especially on BIT ... If possible post videos on suffix array + Lcp by o(n) (without suffix trees) ... just goes over my head ... thanks
there is no reason to continue when 'x' at position 7 has palindrome of length 5, which is less than the 9 found so far, so your explaination since 7:30 makes no sense to me, also since 'y' at position 10 in the 2nd case has palindrome of length 11, there is no need to continue since 13:40 because you cannot find a palindrome which length is larger than 11